Minimum Platforms Problem | Greedy Algorithm | DSA-One Course #98
Minimum Platforms Problem | Greedy Algorithm | DSA-One Course #98
Hey guys, In this video, We will learn how to solve the minimum platforms Problem using the Greedy Algorithm.
Problem statement: Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting.
Practice here: https://practice.geeksforgeeks.org/prā¦
š„³ Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
š Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumarā¦
Linkedin: https://www.linkedin.com/in/sharma-kuā¦
Twitter: https://twitter.com/realanujbhaiya
šø Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
š Complete DSA Playlist: Ā Ā Ā ā¢Ā DSA-OneĀ CourseĀ -Ā TheĀ CompleteĀ DataĀ Stā¦Ā Ā
Complete Android Development Playlist: Ā Ā Ā ā¢Ā AndroidĀ DevelopmentĀ TutorialĀ forĀ Begiā¦Ā Ā
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
minimum platform problem
minimum platforms
anuj bhaiya
minimum number of platforms required for a railway/bus station
minimum platforms needed in a railway station
greedy algorithm
minimum number of platforms required for a railway
java anuj bhaiya
dsp anuj bhaiya
gas station leetcode
activity selection problem using greedy method
greedy algorithm playlist
anuj bhaiya java
anuj kumar sharma
divide intervals into minimum number of groups
dsa one
minimum platforms gfg
2406. divide intervals into minimum number of groups
greedy
job scheduling
minimize the difference between heights
minimum platform
big o notation
code with harry
codehelp love babbar
dsa algorithm
dsa one course
fraz
gaurav sen
greedy algorithm adithya varma
greedy algorithm java
greedy algorithms
greedy playlist
greedy search
job sequencing problem
kadaneās algorithm
love babbar code help
minimize the heights ii
minimum no of platforms
Content
0 -> Hey guys what's up Anuj here
0.976 -> and welcome to the DSAone course
2.005 -> in today's video we are going to talk about another
3.558 -> great question on greedy algorithm which is minimum platforms.
6.238 -> It's a very generic questions, it's been asked a lot of times,
7.913 -> I myself was asked about this in two interviews.
9.936 -> So, today we'll understand how it works.
11.909 -> We have already done two questions on greedy algorithm
14.499 -> after this we'll move ahead on our DSAone course.
16.556 -> Questions is:
17.403 -> You have to design a station,
20.445 -> you know by designing that station that how many trains in the future will come on it,
24.97 -> we know no trains will come on this station apart from these six trains.
29.135 -> So you have to tell how many platforms are required,
31.933 -> minimum platforms it'll take to accommodate all the trains.
36.088 -> You are given their schedule,
37.585 -> What's the arrival, and the departure.
40.107 -> Arrival is at 9:00 for this train,
41.686 -> it will go at 9:10.
42.685 -> The second train will come at 9:40,
43.958 -> it will go at 12:00.
44.921 -> Third train will come at 9:50, and go at 11:20.
46.558 -> And so on.
47.303 -> So you have to tell what's the minimum platform requirement to accommodate every train
52.578 -> on this station.
53.756 -> To do this questions, again it's a very intuitive question,
57.129 -> one train is from 9:00 to 9:10,
60.357 -> second train will be from 9:40 to 12:00,
63.401 -> 9:40 to 12:00,
66.414 -> third train will come at 9:50,
68.211 -> that is, start from here and end at 11:20.
70.584 -> Which means they are overlapping.
71.867 -> If two trains are overlapping then we need two platforms,
75.27 -> we won't be able to do in one platform.
77.787 -> After that, next comes on 11:00,
79.879 -> so this one ends at 11:20,
83.018 -> comes at 9:50.
85.104 -> After that the next one comes at 11:00,
87.275 -> leaves at 11:30.
88.629 -> That means from here to there.
92 -> This is the third trains.
94.344 -> And this comes at 11:00,
96.115 -> and leaves at 11:30.
98.844 -> The train after that comes later, at 3:00,
102.069 -> till 7:00, so it's the 24 hour format.
105.99 -> 1900 here.
107.724 -> And the other train comes at 1800,
109.279 -> and goes at 2000.
111.125 -> So in this way we have made all the overlapping,
113.706 -> where all of them overlap.
115.611 -> And if you find out where the maximum overlaps are happening
120.343 -> then that is the no. of platforms required.
121.793 -> We can see here is the maximum overlap.
124.621 -> That means we at least need three platforms.
126.891 -> There are two overlaps here too, but don't worry,
129.026 -> there are three overlaps here,
130.747 -> we need to find out the maximum overlap.
132.345 -> If you find out the maximum overlap then you can find out the minimum platforms.
138.963 -> So, at least, you need three platforms,
142.024 -> minimum three platforms are required to accommodate all the trains.
145.578 -> So we need to find out about the overlap,
147.377 -> how can you find out about the overlap, think about that.
149.198 -> One method which is very amazing,
150.902 -> that you start travelling from here, keep travelling left to right,
156.09 -> and whatever you find, whether the starting or ending time,
159.324 -> whether it's the arrival or departure time,
161.583 -> increment or decrement your count variable according to what you get.
165.286 -> So we'll make a count variable
167.202 -> and with that create a max variable,
169.312 -> so that you always have maximum count because
171.108 -> maximum overlap will get you minimum platforms.
173.285 -> So we'll start travelling from there, first we get here,
175.423 -> which is an arrival time, this is an arrival time.
177.906 -> So our count is 1, it'll increase.
180.93 -> Then we got this, which is the departure time,
183.415 -> 9:10 is the departure time, so we'll decrement our count,
185.977 -> it will become 0.
187.177 -> But the max will remain 1,
188.526 -> max has been updated, at least 1 platform is needed.
191.366 -> Then we'll move ahead, we'll get this at 9:40,
193.641 -> which is an arrival time, that means we have increment again.
197.273 -> Next we'll get this, which is also an arrival time
200.238 -> which means we have to increment once more,
202.021 -> you see we need 2 platforms here, so we need 2,
205.102 -> and we'll update max, max will be updated along with the maximum value.
209.407 -> We'll go ahead, we get this, 11:00,
211.358 -> that means third train is coming, this is also arrival time,
214.53 -> which means it'll increase again,
216.885 -> and we'll increase max to 3.
219.242 -> Then the next we'll get is 11:20,
221.594 -> 11:20 is a departure time.
223.28 -> This is a departure time, so we have to decrement from 3 to 2.
226.473 -> We won't update max,
227.445 -> then the next we'll get is 11:30,
229.228 -> which is also a departure time so we will again decrease it, 2 to 1.
232.099 -> After that we get 12:00, also a departure time,
235.4 -> so we'll decrease from 1 to 0.
237.62 -> Then we'll move ahead,
239.09 -> moving ahead we get 15:00, which is an arrival time
241.658 -> so we'll increase it, so by changing count variable only we get the answer.
247.533 -> We'll check, is it more than the maximum, it's not,
249.94 -> so we won't update maximum.
250.996 -> Then the next is 18:00, so we'll again increase it, 1 to 2,
254.907 -> You can see you need 2 platforms here,
257.474 -> after that we get 19:00, which is departure so we'll decrease.
260.58 -> Then we'll get 20:00, which is also a departure time so
262.729 -> we'll decrease it.
263.599 -> After that we'll see, what's the answer in maximum,
265.715 -> the answer is 3 inside max. which means there were 3 maximum overlaps.
268.984 -> And in this way, this questions is done,
271.303 -> you don't have to see which train is arriving or departuring,
275.747 -> you don't have to see that, you will consider all trains the same.
279.124 -> You just have to look at the arrival and departure time,
281.749 -> is this the arrival or departure time.
285.134 -> So, how can we solve this question, code it.
287.231 -> You are given these two arrays,
289.232 -> just sort these two arrays,
291.421 -> sort arrival and departure separately.
294.224 -> There's no need for a co-relation between them.
296.346 -> You just care for the arrival and departure time.
299.575 -> So you sort this separately and this also separately.
301.584 -> After that keep two pointers,
303.677 -> one for arrival and one for departure time.
305.817 -> Keep checking which one is smaller,
307.144 -> according to that you'll change the count.
309.711 -> So I'll code this now, it will be very simple
312.348 -> after that it will be more clear to you.
314.376 -> So this is the code, find platforms.
316.061 -> In this we are given arrival and departure time array
319.876 -> and also given total no. of trains.
322.269 -> First of all we'll sort arrival and departure,
325.131 -> like I told you, after that we'll create a variable
328.425 -> named count in which we'll keep, what's the current count.
331.077 -> And this is max., I have named this answer.
333.844 -> After that we'll keep two pointers here,
336.33 -> 'i' will be in arrival time,
338.086 -> 'j' will be in departure.
340.731 -> While 'i' is less than 'n',
343.929 -> I am just checking with the arrival one, while 'i' is less than 'n'
346.702 -> because arrival pointer will finish early.
348.867 -> Departure will be done lately.
350.605 -> So, I have two pointers here, one is in arrival array,
353.743 -> other is in departure array.
355.094 -> This is 'i',
356.531 -> and this is 'j', I'll check
358.033 -> which one's smaller,
359.269 -> the one which is smaller, that will be the first one,
362.546 -> because we are travelling from left to right,
364.217 -> so I'll see 9:00 is smaller,
366.584 -> which is an arrival time,
367.646 -> that means I have to change my count.
370.299 -> And then move ahead in the arrival time.
372.459 -> So that is what I did, did count++,
374.457 -> and then I updated the answer,
376.973 -> as I changed the count, I also updated the answer.
380.249 -> And after that I did 'i'++,
382.037 -> move ahead in arrival array.
383.725 -> If that's not the case, then that means this is departure time
387.694 -> this point is departure time,
390.545 -> so we'll do count--,
393.298 -> and tell 'j' to move ahead in departure array.
396.233 -> And do that again and again,
397.988 -> and finally we'll return answer.
399.305 -> So in this way, this is easily done in nlogn.
402.497 -> We don't require any extra space,
404.253 -> and we'll run it.
406.926 -> So with this we have done a lot of questions on greedy algorithm
410.085 -> we'll be moving ahead in DSAone course now.
411.687 -> That was all in this video, I'll see you guys in the next video.
414.07 -> Like this video, Subscribe the Channel,
I'll meet with you in the next one.
416.587 -> Bye, Bye!
Source: https://www.youtube.com/watch?v=Ls_AYoz1IX0