Minimum platforms needed in a railway station
Vložit
- čas přidán 20. 09. 2019
- This is a very interesting programming question which requires you to find out the minimum number of platforms needed in a railway station or bus station so that no train has to wait and every train gets a platform for itself in the scheduled time. This video lecture explains one brute force method followed by the optimal approach. CODE LINK is present in the description below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
Thank you so much for your efforts! Have been following your videos for long now, it's very helpful
I follow your channel and every problem explained is unique and real life based.
All the best, you're doing great 😁
Your motivation is proceless :)
Thanks a ton, was struggling with this question for a long time. You video made it damn easy!
Welcome :)
could you explain the code for the brute force approach? Thanks.
The way you explain makes the thing very easy for us.. thanks you so much.. keep going..
Welcome :)
Hey, hope you are doing good, can you please explain why we sorted arrival and departure separately, haven't we lost the info about time period for which that train is gonna be on platform?
Hey, I am good. We don't need to keep the context info (that is which train arrived when and departed) specifically. We just need to know the number of trains at a station and not what train. So, we can take a pair and store info in array of pairs. Now sorting by say departure time will easily let us know about number of trains at a particular time at station. We don't need to worry about order here. So, sorting won't change or effect our answer.
departure time slots are related to the train that is arrived at particular time.how can you only sort the departure time array?
Hey @TECH DOSE,
your brute force solution is incorrect. I'll explain it with 2 cases.
1. Nested intervals that merge.
arrivals - {940, 950, 1100}
departures - {1200, 1120, 1130}
Here we need 3 intervals according to your brute force solution which is correct. (Because max intersecting intervals is 3).
2. Nested intervals that do not merge.
arrivals - {940, 950, 1130}
departures - {1200, 1120, 1150}
Here, the brute force solution would return 3 (Because max intersecting intervals is 3). But the answer is 2. Why? The train from 940 to 1200 would need one platform. But the other 2 trains can be handled at a single platform.
Still we will get 2
yes you are right............... when i was thinking about the solution, i also thought about the same case if that's not the case question become too easy !
A very good point. I was facing issues trying to make the brute-force run on geeksforgeeks, something was being overcounted. Now I see this was the issue. Thanks!
Thanks for your effort. Keep it rock brother!
:)
Thank you for the tutorials about problems, kindly keep making more
Okay
You made it look sooooo eazyy.... 😍😍
Thank you...
if we sort the arrival and dep time then the order of arrival and departure time of each train will be differed,then why u sorted ?
Good work yaar. Would love to see your channel grow beyond numbers.
Your motivation is irreplaceble :)
I guess how you approach the problem and intuition behind the problem is more important than solving the problem. Can you explain more about the intuition and why this approach solves the problem? Sometimes is easy to get that in your videos after you see the answer but I would like to see your thought process before the answer. Thank you
This intuition is simple but most people slip such ideas. In order to understand the intuition, you should first know about the critical conditions which leads to this intuition. CONDITION: Every train is similar and we don't care about what train is coming or going. We are only concerned about their timings of arrival and departure. DIFFICULT APPROACH: People start taking train's arrival as well as departure time and maintain them at the same index of array. They sort arrival array and correspondingly swap the departure array elements (so that every train's departure time is at the same index of that of arrival time and vice-versa). If you think more about it, we don't really care about maintaining the train intervals correspondingly. APPROACH: We sort both the arrays. This tells us in chronological order, when a train is gonna leave a station and vacate a platform and when a train is gonna arrive and acquire a station. Now when we move chronologically then we can easily keep track of the number of current trains at our station (using 2 variables). Max_value of this number gives the minimum number of platforms needed so that the station works seamlessly and no train has to wait. I HOPE YOU GOT YOUR ANSWER :)
@@techdose4uIt's now more clear to me and I love your explanation. I would love to see this kind of explanation in all your videos since it makes your videos more valuable. Thank you so much.
@@techdose4u particular train ke dep and arr time interval ka koe sense nhi tha to diya hi kyu hai.... random de dete ki kisi train ka arr and dep time ka arr given hai......
please explain i didn't get it
I want a playlist on DP. Thank you for your good work.
I will keep adding videos :)
Thank you sir for crisp clear explanation. Can we do this problem using heap sort and can improve average performance?
I am a little late, but to those who are asking, think this way...
Sorting only departure time works is because the arrival time will always be less than departure time of a particular train. Hence, to find at which time the number of trains at the station were maximum, all we need to do is sort the departure time array, and then compare them as mentioned in the video.
Also, i have a query...
If we use the Pinned comment's method, but only one array to store info about all the trains, then we can possibly reduce even more space, by using the o(1) of how to add a number in an array in a given range
This one is giving error
vector pre(5000,0);
int m=0;
for(int i=0;i
why dep and arr sorted separately not in pair bcz train indexing change if sort separately ?
Same question.
how can you change the departure time of the plain, isn't they must be sort in pairs ?
Please read the pinned comment of Wei wang
I feel bruteforce will not work for
arr: 1500 1505 1610 1810
dep: 1900 1605 1710 1855
It will give 4, but actually it should be 2
Which algorithm is used for this logic
Can we use greedy in this solution?
What about the fact after sorting we lose departure time of the trains i.e. we don't know which train we leaves when, won't it create complications....
We actually don't care about the very specifics of a train. Read the pinned comment of Wei Wang. You will understand.
sir if the depareture time and arrival time for two different trains are diffferent then which pointer should be move first , i or j do you need to increase the max_platforms in these case
we should increment the pointer that points to smallest value and max_platform increment based on pointers incremented.
Why I am not able to apply similar logic which is count overlapping intervals and after than take the max variable to update our ans I am getting wrong answer from this
thank you for this video
Why are we sorting the arrays? I understood the solution u came up with bud didn’t understand how u came up with that… anyways great work👍🏻
Very good explanation😊
is it possible to use bubble sort for sorting the elements?
Just use library to sort in NlogN.
Nice Explanation. Please make more videos of codeforces and Codechef.
Sure :)
Can we use this algorithm in real life? In what way?
sir how did you prepared for gate cse as you are from mettalurgy branch,i am also a mechanical engineering student from nit calicut and i want to prepare for gate cse but have only few months left as i became 4th year now
Before studying see what options do you have. I was rejected by all indian colleges based on degree and accepted by only 1 college. It's almost impossible to change to CSE. First do some research whether you will be eligible for counselling.
very clean explanation
Explanation is very good, could you please provide the c code for this problem?
Convert my code to C. Don't use substr, instead just traverse the string and copy char by char. Time will still be the same.
why this algo works ?? like you are sorting both arr[] and dpt[] separately. I think we will lose some information. Can you please justify.
We dont bother about train identify.We just bother about count of trains here.Therefore we don't need the information which you might be thinking of preserving.Please read the PINNED comment of Wei Wang.
why we sort the array?
isn't this problem a variation of activity selection problem?
Why did you sort it???
what if arr[i]==dept[j]???
I don't understand why the arrival array is independently sorted from depart array
wow thanks for the explaination
Welcome
Need to sort both arrival and departure?
No...anyone will do...
very clear and awesome explanation
Thanks :)
@@techdose4u alwz welcome 😊
Quite confused by your approach, the main confusion I encounter u are independently sorting arrival and departure array, that's quite strange. Please solve greedily like Activity Selection Problem
Please read the pinned comment of Wei Wang for better understanding.
why did we start from the second position in the arrival array ?
this is because he started with max_platforms = 1, if he would have started from max_platforms = 0 he would have taken arr[0]. The reason is its obvious that we will always pick arr[0] first as arr is in sorted order and arr[0]
nice one thanks bro
Welcome :)
My solution will be.. to sort all the start and depart time and sort those.i should not concerned with departure.
In linear way i will count +1 -1 .. max value will be the number of platform
Create a playlist for arrays, strings.
I am doing the same currently :)
Although I got the code part of what to do to solve this problem still I am not able to understand why this logic works? I mean sorting ONLY the departure time distorts the given data so I have a feeling that the wrong result might come. It would be nice if you can explain/provide some source for the logic. For the code part, Same thing present here: www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
Sorting works because if you draw a time line of train timings side by side (vertically) then you will need to find the max intersection size of these lines. I have pinned the comment of WEI WANG. Have a look at it and you will get the logic :)
I did not understand why both arrays have been sorted since after sorting we are losing information of which train has what arrival and departure time ? can someone help me ?
don t think that way, think like this- we don t need to keep track of which train's arrival time was that or which train's departure time was that, what we need is only the times.
For each departure time, we find the maximum arrivals which is nothing but the number of platforms needed.
And then we keep just take the maximum of the platforms needed for each iteration(above statement)
That is our ans. Hope this helps you to get the intuition
Can u explain the brute force approach too? I didnt understand.
For max number of trains at a time on platform, atleast one will be present on station. So, we will fix one train interval and count how many trains have come and gone within that time interval. This will give the number of trains in a range. If you don't understand what i said then just think simply how will you find out the max no of trains in a station at a time. You will use your intuition and take interval and find the number of trains in that interval. Again you will take some other interval and repeat the process. Finally you will take the max value as your answer. I hope you will get it cleared once you do it yourself. Just try it :)
@@techdose4u Yes, i needed to sort by arrival times and then brute force it.
This video is really good 👌👌and for those who are saying the information is lost because we sorted both the arrays,i will just say that no information is not lost since it was not needed in the first place.Think about it we are increasing the no of platforms because the arrival time of the current train is before the departure of the previous train to which out 'j' is set that's why for this current('i') arriving train we need one more platform thus we end up increasing the number of minimum no of platforms.
As for the code :-
int findPlatform(int arr[], int dep[], int n)
{
sort(arr,arr+n);
sort(dep,dep+n);
int pf=1;//considering we need platform for 1st train
int j=0;
for(int i=1;i
:)
it would be great if you would have provided the code too for reference
Yea right. I am keeping this in mind and providing codes.
Same as Leetcode 253: Here is the implementation in python:
class SolutionWithChronology:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
starts = [interval[0] for interval in intervals]
ends = [interval[1] for interval in intervals]
starts.sort()
ends.sort()
active_rooms = 0
s = e = 0
while s < len(starts):
if starts[s] < ends[e]:
# current meeting will end in a while. Must allocate new room
# and move the start pointer
active_rooms += 1
s += 1
else:
# one meeting just got over. Reuse.
# No need to allocate new meeting room
e += 1
s += 1
return active_rooms
Thank you sir
Welcome
thank you
Welcome :)
can you post the source code in the link.
Okay will do it :)
Sir you are god
😅
do you code for this
Yea
every one talking so much technical term that i got confused thank to god that i stumbled upon this video
:P
this isnt the fastest solution, it can go till O(N)
👍
static int findPlatform(int arr[], int dep[], int n)
{
Arrays.sort(arr);
Arrays.sort(dep);
int ans=1;
int need=1;
int a = 1 , d = 0 , i=0;
while(a < arr.length){
if(arr[a] > dep[d]){
need--;
d++;
}
else {
need++;
a++;
}
ans = Math.max(need,ans);
}
return ans;
}
Agar algo implementation ke video hi banane hai to kya hi faeda vo to gfg pe bhi hai atleast kuch to algo ke peeche ka intution batana chahiye tha...video to bas simply algo ko implement kra ke dikha dia hai
please let me know why we sorted the arrays? Basically after watching the video, I could write a code on this problem but I didn't understand the logic well. please help.
Sorted because order of trains doesn't matter. Please read the pinned comment by Wei wang.
@@techdose4u No, I didnt understand his solution, moreover I wanted to know the logic behind your approach sir, it will be really helpful if you could help me with that.
@@nehaltiwari6132 may I explain you
@@ritiksolanki6267 please do!
@@nehaltiwari6132 let's take an example
There is a classroom with no bench at all
And there are 10 students and all of them comes to class at different time.
So what we'll do...as a student come we...we will see that if there is no bench empty...we will put one more bench in classroom for that student.
Arrival time Departure time
1. 10:00 2:00
2. 10:20 10:40
3. 10:30 10:50
4. 10:50 11:00
5. 10:40 11:20
Now see,
As the classroom is empty at first,so definitely we have to put first bench for that particular student
Now as we know,he will depart from class at 2:00 so till that time that bench will be acquired. We can only allote that sit to other student after 2 o'clock
Now second student come at 10:20 so we have to give a new bench to him as there is no any sit empty
And then 3rd student arrive at 10:30, we have to give new bench to him too....
But as the 4th student come at 10:50 we know that 2nd student was departed so we can allow that bench to 4th student
And when 5 th student arrive....we know that 3rd bench is free so we can allote that bench to 5th student
So basically what we are doing
Finding out the student who departs first, without considering that he/she was first to arrive in class or not
So we are arranging first arrival time of all the students in ascending order
And then arranging departure time of all the students so that we can find which bench was getting empty first so that we can allote it to other student
This same concept will apply to minimum platform question.....it doesn't matter which train will arrive at station first....we also have to see that which train will depart first....so that we can allote that platform to upcoming train.....
Hope you will get it.... actually it is tooo difficult for me to explain this concept by comment😅😅...but then tooo...I tried
Plz share source codr
CODE LINK: www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
logic nahi samajh aaya acche se
Not railway obey now.. Ok
i cant understand 😭
Read pinned comment.