L10. Minimum number of platforms required in a railway station

Find problem link, notes under Step 12: takeuforward.o...
Follow me on socials: linktr.ee/take...

[@shashwatkumar6965]

We can also solve it in O(N) TC and O(1) Space: Since the time is in 24hr format, we can keep a time array of size 2360 (max time = 23:59) Then for evey minute count the number of trains present Finally loop through the time array and take the max count Eg: arr[] = {1000, 1030, 0900}, dep[] = {1100, 1130, 0945} So, in time array from 0900 till 0945 count will be 1, then from 1000 till 1030 count will be 1, but from 1030 till 1100 count will be 2 and from 1100 till 1130 count is 1. So max count is 2 which is the answer. So in this case we dont need to sort the array, we can just keep the count of trains at every minute. Code: vector time(2360, 0); for(int i = 0; i < n; i++){ for(int j = arr[i]; j

[@drishtiambastha3141]

but nested for loop causes O(N^2)

[@shashwatkumar6965]

@@drishtiambastha3141 The nested for loop can run upto max 2360 times for every ith element which makes TC = O(N * 2360) ~= O(N)

[@thoughtsofkrishna8963]

But log(n) value is lesser than the 2360,

[@shashwatkumar6965]

@@thoughtsofkrishna8963 no its not. O(2360) ~= O(1) and O(log n) > O(1)

[@jaydabhi240]

​​@@shashwatkumar6965​ it's not always like O(constant)= O(1). well theoretically it is true but practically not for example if in constraints it is given that 1

[@worldfromhome4033]

This explanation is so much better and intuitive than the previous video!! Thanks Striver

[@akashvines0509]

Waiting for Heaps and strings playlist 🙌👍

[@KumarjiIndia]

See Aditya Verma playlist

[@kagathal]

This what I managed to do without watching Striver's video. Let's see how off I am and where all I make improvements. class Solution{ /* KeyPoints(KP):- 1) Arr and Dep int arrays are given. 2) No train must be waiting. 3) Minimize the no of platforms taken. 4) Arr[i] != Dep[i] but Arr[j] may be equal to Dep[i] for i!=j. 5) Even if Dep[i] == Arr[j] for i!=j, same platform cannot be used. Observations(OB):- 1) Makes sense to sort the array of trains by their departure time. 2) If there is some overlap between Arr and Dep of 2 different trains, new platform is needed due to KP5. 3) If we say during time t = Arr[i], no of trains in wait is increased by one then we can say we t = Dep[i] + 1, no of. trains in wait is decreased by one. 4) The OB3 implies we can use a sweep-line algorithm with prefix sum to know at time 't' how many trains are in wait. 5) OB4 also implies that if we just find the max value in the prefix sums array, we can know how many platforms are needed at most as if we say 3 platforms are needed at most for day, then at no point in the day would we need more than 3. Algorithm Analysis:- -> First we sort a custom trains array, hence T = O(nlogn) & S = O(n). -> We create an array to store no of trains in wait during time 't'. This means an array of size (2400, ie no of hours in one day) ie S = O(1). -> Iterate through all train objects, incrementing Time[arr[i]] by 1 and decrementing Time[dep[i]] by 1. -> Traverse from t = 0 to t = 2359 and modify the Time array to a prefix array. -> Return the max value from Time array. Hence, T = O(nlogn) , S = O(n). */ public: //Function to find the minimum number of platforms required at the //railway station such that no train waits. int findPlatform(int arr[], int dep[], int n) { // Your code here vector trains; vector trainsWaiting(2401); for(int i = 0; i < n; ++i){ trains.push_back({arr[i], dep[i]}); } sort(trains.begin(), trains.end(), [](vector& a, vector& b){ return a[1] < b[1]; }); for(auto &train : trains){ trainsWaiting[train[0]]++; trainsWaiting[train[1] + 1]--; } for(int t = 1; t < 2401; t++){ trainsWaiting[t] += trainsWaiting[t-1]; } return *max_element(trainsWaiting.begin(), trainsWaiting.end()); } };

[@tanujaSangwan]

A very easy approach keep a vector of size "24*60+1" size and for every train keep check how many trains are present at that minute of time. Return the maximum of the vector. Easy and intuitive O(n) approach

[@Bunny-kn4hi]

Do you mean to say that for every train you will increment +1 from arrival minute to departure minute??? If we follow this approach The worst case time and space complexity: Space: 24-60 + 1 = 1441 For every train you will iterate from arrival_min to depart_min and do +1. IN worst case you might have to iterate complete array i.e. 1441. SO for n trains TC = 1441 * n as per problem n can be max 50000 SO TC = 1441 * n = 7.2 * 10^7 IS this not slow?

[@tanujaSangwan]

@@Bunny-kn4hi Yeah. Not optimal

[@darshitakumar7913]

What a beautiful optimal solution! 😄

[@venumsingh]

This is cleverly crafted problem of meeting rooms.

[@ababhimanyu806]

why we cant use that approach in this question?

[@jotsinghbindra8317]

@@ababhimanyu806 udhr ek room me hi meetings krni thi toh T/F hi bs judge krna tha hr meeting pe and count dena tha , yaha multiple rooms le skte ho toh multiple rooms ki entry and exit ko dekhna prega ,usko manage kaise kroge?(you cant make a seperate vector for it nhi toh fir baar baar iterate krna prega usko extra TC aayega)

[@abdelrhmantarek3937]

@@ababhimanyu806 N rooms u were searching for nonoverlapping intervals so u need to sort by end time , but here u are looking for overlapping intervals so u will sort by the start time

[@ToonDubberDuo]

@@ababhimanyu806 you can do it but while keeping prev array for the previous interval you need to use a heap , to check the overlapping intervals simulatenously, i did it that way and it worked

[@chiragmaheshwari6761]

@@jotsinghbindra8317 but we can keep the count of things that are not fitting to our time interval that no of diff platform we require + 1

[@sanchya9122]

The brutefore will give wrong answer take example : (1,7) ,(2,3),(4,5) no of overlaps for (1,7) will be 2 but (2,3) and (4,5) are not overlapping hence can be on same platform so ans wont be 3 it would be 2. check code for this input: int arr[]={900,945,955,1100,1500,1800}; int dep[]={920,1200,1000,1150,1900,2000};

[@prateekrajput2646]

Fails for below as well 900 1000 1100 1200 1010 1150

[@elitegamer-pit09]

i think prefix sum is a good approach.

[@svmepisode]

correct answer is int findPlatform(vector& arr, vector& dep) { // Your code here int ans=1; //final value int n = arr.size(); for(int i=0;i= arr[i]) { count++; } } } ans=max(ans,count); //updating the value } return ans; }

[@Akash-Bisariya]

You made this question looks so easy. Wow!!

[@SukritAkhauri]

This is one of the finest solution, i have seen striver. It is really waoo. Good job, keep sharing the learning with us.

[@huungryyyy]

Like I was thinking that why are you making the same video again but when i saw both the videos i got shocked by the improvement in your teaching skills bhaiyaa i didnt get this question in the previous solution but when i saw this explanation i got all my concepts cleared. Thanku so much striver for this brilliant explanationn.😊😊🙂🙂

[@kevalkrishna4134]

Ur explanation has become good as compared to ur previous video on the same question ,a lot better

[@jritzeku]

Visualization/Intution that helped undertand why we sorted the departure data: - Firstly, notice that the time pairs(arrive,depart) is NOT same as depart,arrive like in airplane. ->when train arrives, its jus sitting at station doing nothing! With that said, we do not have to view arrive , depart as one unit of data tied together. -So the person responsible for clearing assigning tracks is basically just looking at his clock the whole time!! ->After every few minutes, he is going to do one of 3 things: -do nothing (neither arrival not departure happened) //no need to code this -clear a track (becuase it departed) ->to do this, it would be convenient for the depart times to be in sorted order. -open new track (because new train arrived before an old train departed) ->to do this, it would be convenient for arrival times to be in sorted order -NOTE: arrival times are by default given in sorted order so idk why we had to sort it.

[@ADG-ob4xi]

nice explanation man, really helpful

[@k-nl4kj]

we have to sort arrival time because all testcases don't have sorting so to pass all testcases we have to sort arrival time also

[@Echo-942]

// Comparator function to ensure that departures are processed before arrivals when times are equal static bool comp(pair val1, pair val2) { if (val1.first == val2.first) { // If times are the same, give priority to departure return val1.second < val2.second; } return val1.first < val2.first; } int findPlatform(int arr[], int dep[], int n) { vector clockArray; // Create pairs of (time, 'A' or 'D') for all arrival and departure times for(int i = 0; i < n; i++) { clockArray.push_back({arr[i], 'A'}); // 'A' for arrival clockArray.push_back({dep[i], 'D'}); // 'D' for departure } // Sort the events by time, with departures before arrivals if times are equal sort(clockArray.begin(), clockArray.end(), comp); int MaxCount = 0; int count = 0; // Traverse the sorted events for(int i = 0; i < 2 * n; i++) { if(clockArray[i].second == 'A') { // Train arrives, increase the platform count count++; } else { // Train departs, decrease the platform count count--; } // Update the maximum number of platforms needed MaxCount = max(MaxCount, count); } return MaxCount; }

[@drrrpp]

arrival depature count approach is excellent

[@naveen_satyarthi]

class Solution { public: // Function to find the minimum number of platforms required at the // railway station such that no train waits. int findPlatform(vector& arr, vector& dep) { // Your code here sort(arr.begin(), arr.end()); sort(dep.begin(), dep.end()); int i = 0, j = 0; int n = arr.size(); int max_count = 0; int required = 0; while(i < n && j < n){ if(arr[i]

[@kkartik7]

you standing at the railway station and counting was brilliant

[@subhashchandra6654]

solve all intervals questions using SWEEP LINE ALGORITHM

[@Dsa_kabaap]

Sir please start making videos on strings and stacks

[@Oracle-cruX]

Hi, the initial approach seems incorrect , consider timings as {(10,12),(11,16),(13,14),(15,17)} , here 2 platforms work but the brute force code gives 3 as answer

[@harshalrelan3113]

exactly the same doubt thanks for pointing it out

[@akshaykolluru962]

I think the brute force solution is wrong here for Ex:(1000,1030),(1010,1015),(1020,1030) Here max intersections are 3 but ans is 2

[@aartibhatnagar3989]

great observation skills

[@travelsphere1414]

Exactly what Im thinking about!!

[@twinklelight9829]

can u please explain why this approach failed..? what went wrong in the thought process?

[@vamsikrishnagannamaneni912]

Sort by time, but if times are the same, prioritize 'D' (departure) over 'A' (arrival), If using time lapse approach

[@krrishagarwal8479]

why

[@YazhiniSelvakumar-g7p]

great explanation ever😍

[@krishnakanthati]

I understood the brute. Max overlaps = Min platforms

[@kondalaumamaheshwararao2697]

yes, waiting for Heaps and strings playlist

[@suhasherle7350]

Really brilliant explanation

[@SAICHARAN0321]

Waiting for string and stack queue videos more

[@AKASHKUMAR-li7li]

We can easily apply sweep line algorithm👍

[@aryankamal1196]

beautiful intuition !

[@UECAshutoshKumar]

Thank you 😊

[@KaranVerma-pf5jw]

There is a problem with the brute force approach , change the 3rd index arrival time from 1100 to 1140 in the given example and you will see the approach will still give 3 as answer but it's correct answer is 2. From there you can figure out where the problem is in the approach.

[@svmepisode]

this is correct answer for brute force approach int findPlatform(vector& arr, vector& dep) { // Your code here int ans=1; //final value int n = arr.size(); for(int i=0;i= arr[i]) { count++; } } } ans=max(ans,count); //updating the value } return ans; }

[@apmotivationakashparmar722]

Thank you for great Explaination.

[@kaichang8186]

understood, thanks for the perfect explanation

[@iscommendable13]

eagerly waiting for heap and string playlist

[@shashwatkumar6965]

This approach is also known as Line Sweep Algorithm and it can be used to solve many interval related problems.

[@karthik-varma-1579]

great sir

[@rishi496]

class Solution { public: // Function to find the minimum number of platforms required at the // railway station such that no train waits. int findPlatform(vector& arr, vector& dep) { int n = arr.size(); int platform = 1; sort(arr.begin(), arr.end()); sort(dep.begin(), dep.end()); int maxplatform = 1; int i = 1; int j= 0; while(i

[@neetameshram9141]

Understood! As the time goes by 😋

[@namrathabejgam]

Another (unpopular?) approach: We can solve it like how we solve "Array Manipulation" from hackerrank (leetcode discuss thread available on the same with title "Minimum number of platforms required for a railway", unable to link it here probably because of restriction)

[@bhavatearya]

excellent

[@gaganbajpai3310]

Bhaiya strings and heaps ki playlist kab la rhe

[@I_tanishmittal]

This problem is exactly similar to (CSES - Restaurant Customers) ... must check it I'll suggest ! Another approach : (nlogn) -> Take arrival and depart times in a pair of vector and sort on the basis of depart time. Now you can use a multiset named platforms (storing the depart time of last train on each platform) initially storing only one element {-1}, Now iterate from 0 to n-1 and use lower_bound function to find suitable platform for each train (if available else add new platform) ... finally return size of this multiset platforms.

[@shashankvashishtha4454]

understood

[@subee128]

Thanks

[@JayakanthS]

Pls continue this

[@shubham.s8934]

O(n) code int findPlatform(int arr[], int dep[], int n) { // Arrivals and Departures in sorted order vector arrival(2401, 0); vector departure(2401, 0); for(int i=0; i

[@ravimakwana992]

genius!

[@DeadPoolx1712]

UNDERSTOOD;

[@iamnottech8918]

bruteforce is not at all intitutive but ya its a good concept

[@bhagwadgeeta_4820]

In the basic approach why are we taking the maxCount? Aren't we required to find the minimum no of platforms required. Can any one please explain

[@krishnavamsireddyduggiredd8539]

why sliding window after sorting is giving wrong answer for this question?

[@rishikakinger7608]

beautiful

[@gauravkhatri3316]

3 0930 1010 1110 1210 1100 1200 Your Output: 3 Expected Output: 2 according to your brute force method this code will not work

[@madhuellappan5743]

I know by sorting we can get the answer but how come we change the train departure timings by sorting. That's not possible in real life.

[@shailendrakk6226]

Hi Striver sir, I want to become expert in DSA and I am able to think 50% question for O(n2) but 50% not, Can you guide me pls?

[@dababy2882]

Why did we sort departure time independently? Wouldn’t it change the question? After sorting the departure time of train will change and the whole question will be changed. Someone please answer

[@smarajitadak6681]

The main concept lies in finding the timings when the platform will be free and busy. After sorting the timings we can easily see the time when a new train will arrive and when the departure of an existing train in an platform will take place. If the arrival time is lesser than the departure time it means that there is still a train in the platform by the time when the new train arrives irrespective of which trains these are in the original array. So in this case we will increase the number of platforms since we will require one more to station the arriving train. And in the else condition we will decrease the numbers of alloted platforms since the departing time is lesser than the arriving time .

[@jritzeku]

I too had this question. There is more dicussion in the older version of this problem that Striver uploaded few years ago.

[@tummalapallikarthikeya2412]

@@smarajitadak6681 very nice explanation bro, tysm

[@devmadaan5146]

Asaan bhasha Mai, We sorted acc to time, The clock is ticking!! We find the train which arrived, if arrived then platform++ , if depart then platform --,

[@BoredToDeath2357]

I don't know why my strategy is not working. My strategy is to maximize the number of trains that can fit on a single platform by first sorting the trains based on their departure times. After sorting, I pick the maximum number of non-overlapping trains, mark them as visited, and assign them to one platform. I then repeat this process for the remaining unvisited trains, adding a new platform each time until all trains are assigned. This is not giving the right answer. Does anyone know what could be a potential issue with this? I think my approach should be optimal because, at each iteration, I'm trying to fit the maximum number of trains on the platform and repeat the process for the remaining.

[@ayobrrr]

class Solution: def minimumPlatform(self,n,arr,dep): # code here plat=[] mixarr=[[int(arr[i]),int(dep[i])] for i in range(len(arr))] mixarr=sorted(mixarr,key=lambda x:x[1]) for a,d in mixarr: assignedtosomeplat=False for i in range(len(plat)): if plat[i]

[@kshitijjha6737]

Understood

[@SandipKumarKushwaha-c7x]

T.C O(N) and S.C O(1) class Solution{ public: int findPlatform(int nums[], int dep[], int n) { vector arr(2362); for(int i = 0; i < n; i++){ arr[nums[i]] += 1; arr[dep[i] + 1] += -1; } int ans = arr[0]; for(int i = 1; i < 2362; i++){ arr[i] += arr[i - 1]; ans = max(ans , arr[i]); } return ans; } };

[@ITSuyashTiwari]

solved using min priority queue anyone else

[@vikashtiwari5505]

yeah

[@fazilshafi8083]

JAVA SOLUTION 👇 class Solution { static int findPlatform(int arr[], int dep[], int n) { Arrays.sort(arr); Arrays.sort(dep); int neededPlatforms = 1; int maxPlatforms = 1; int i=1, j=0; while(i

[@anugandulasricharan3735]

Thanks Striver for all your efforts .But Brute Force approach is Incorrect. The correct brute force code is below: public int findPlatform(int[] arr, int[] dep, int n) { int maxPlatforms = 0; // Iterate through each train's arrival time for (int i = 0; i < n; i++) { int count = 0; // Check for each train if it overlaps with the train i for (int j = 0; j < n; j++) { //checking arr[j]

[@rxt740]

will it work for this : (1100 ,1800), (1300,1400), (1500,1600) ? the answer is 2 but your code will give 3

[@aryankumar3018]

noice understood

[@soothingmusicforrelaxation3319]

Hey guyz those looking for a TC:- O( N ) solution and SC:- O( 2365 ~ 1 ) this works vector vect(2365, 0); int ans = 0; int n = arr.size(); for(int i=0; i

[@piyushkala9707]

solution he gave for naive approach and code for naive in tuf is wrong i think 3 0900 0920 1010 1200 1000 1150 just run that code with give input and check output on gfg int ans=1; //final value for(int i=0;i

[@iamnottech8918]

iI solved this question on own using arrival time see this class Solution{ public: static bool comparator(vectora,vectorb) { if(a[0]

[@kunalkumar1964]

Hi bhaiya, how are you!

[@storm19019]

Livestreaming platform

[@harishnaik8164]

wrong bruteforce , wrong logic of optimal solution

[@PritamSingh018]

hii sir

[@anantpawar782]

God takes birth on earth in the form of striver.

[@rushidesai2836]

This is a weird question.

[@yasharthsingh3263]

First comment 😀

[@NonameNoname-f2t]

I came up with my original solution in just 30 minutes , its interesting but bad in TC , TC : O(n) + O(N Log N) + O(N^2) SC : O(2N) class Solution { public: static bool comp(vector &a , vector &b){ return a[0] < b[0]; } int findPlatform(vector& arr, vector& dep) { vector p; for(int i = 0; i < arr.size(); i++){ p.push_back({arr[i],dep[i]}); } sort(p.begin(),p.end(),comp); vector freetime; freetime.push_back(p[0][1]); //first train dep time for(int i = 1 ; i < p.size(); i++){ bool isAvail = false; for(int j = 0; j < freetime.size(); j++){ if(p[i][0] > freetime[j]){ isAvail = true; freetime[j] = p[i][1]; break; } } if(!isAvail) freetime.push_back(p[i][1]); } return freetime.size(); } };

[@SibiRanganathL]

understood

[@rohankar5604]

Understood

[@shalinikumari6050]

understood

[@abhinanda7049]

understood