Minimum Platforms | Greedy Algorithms
Вставка
- Опубліковано 9 лют 2025
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUfo...)
✅Entire Series: bit.ly/placemen...
✅Problem link: practice.geeks...
C++/Java Code: takeuforward.o...
✅Unacademy has launched a subscription that will help you learn and interact with your favorite teacher and will also help you clear your doubts! Check it out here: unacademy.com/.... (use coupon code TAKEUFORWARD to get 10% off)
Join Unacademy's Pinnacle 2021; A Comprehensive and Concise Track to Become an Expert: unacademy.com/...
Check out Unacademy’s Free Classes and tests here (For Desktops):
www.codechef.c...
unacademy.com/...
unacademy.com/...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competiti... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
Hi sir,
Please help with the following doubt:
If we sort the arrival and departure times. Is it necessary that arrival time and departure time will be at same locations for the same train. I mean if a train is leaving at 500 can we be sure it was for the same train which came at 50 can it also be for train coming at 200. Will this affect our platform occupation count.
No it won't because it does not matters na which platform is getting vacant, but if someone leaves it is for sure that the train would have arrived that is why it is leaving, so one plat will go empty na!
actually the idea is a train must leave before it's departure time (it means it must have arrival time
We want to be able to know as soon as a platform becomes available. And that is only possible if the departure times are sorted in increasing order. If we keep the departure time unsorted i.e. mapped to the arrival times and only sort according to arrival times, when we iterate through the arrays, it is possible that the next trains departure time is earlier than that of current train, and our departure pointer is stuck at current train unnecessarily, when it could have been incremented if it was sorted and platform could have been empty. Hope this helps!
sir as a train needs to arrive first to departure then.. shouldn't we just need to give the while condition as only i < n we need to check the dep array as terminating condition
It is very difficult to convince my mind that we need to sort both arrays independently :)
same..if ou got the intution,plz comment back
its kind of hole in the solution. which is not getting filled.
Yess samee
The concept here employed is the train departing from station has to be the one which has arrived prior so it doesn't matter which train is leaving we are concerned only with the platform , if the platform is empty we can divert the new train there
hey , its not that hard if you think it like a simulation problem, that means you are simulating the events which occur earlier to later events. In this way , you can clearly see the choices you have to make for a particular event as you are processing earlier events first. Hope it helps.
Do comment on, should I add face in the video or not? Or shall I continue as I did previously?
C++ Code: github.com/striver79/SDESheet/blob/main/NmeetingsCpp
Java Code: github.com/striver79/SDESheet/blob/main/NmeetingsJava
Instagram for live sessions: striver_79
Please Make Full Maths Course Semesters Wise for Btech,BCA,Mtech and MCA Students
Maths are so hard... Please cover all the maths topics also
I prefer videos without face tbh
I prefer videos without face
I prefer without face. If you want to put it then please make bit smaller.
Idk why people without even completing the video dislike it
Happens, haters all round. But am glad they give a view :P
I like without even completing the video .... >_
It's just law.Even if you see the best video in youtube which may be like a hidden gem or popular there will be dislikes.Because people doesn't accept a video with no dislikes.They just do it for fun or yeah there may be haters.But i don't think these are haters just you people think i it is general trend of disliking like the one who started it just did it for fun as there is not dislike in this way a particular video got dislikes from people like him and some people see this video and sees the dislikes even if it is great come to some opinion and they will continue the trend.Most of the people are from this branch of trend continuation and some people do it for fun and some do it because of hate,dislike,not liking the way they do it and so on.I am just including something there may be some people who are selfish and they don't want everyone to see it so they dislike i think there is a possibility of this given the people i am around with.I don't say this for sure but yeah may be there is a chance these people are out there too.I am an expert of seeing weirdos. So yeah i think there is chance there are these kind of people
@@watchlistsclips3196 Thankyou for this unwanted knowledge
@@unbiasedcrook9157 Well she wants the reason and i am telling that may be this is unwanted knowledge to you but for her she wants to know and i am telling that.
ming boggling method!!...i mean it's really difficult to come up with sorting two related arrays independently...we always try to rule out sorting independently..but here my goodness!!! you are amazing man!
Tried my best to explain:
Eg. 1st train: 6 to 12
2nd train: 7 to 10
1st train which will leave the platform will be at 10. It means any train arrive before 10 will need another
platform (It is leaving means it has already arrived and standing on the platform). And the Arrival is also
sorted that means next arrival will always greater than 6. So, any train which arrive surely after 6 and
may before 10 will need separate platform. Here next arrival is 7, hence needed separate platform
In simple words, any train whose arrival within 6 to 10 will need separate platform
thanks a lot
I found another Simple method by mistake
1.Assume n trains take n platforms (Each train 1 platform ==> count++)
2. Whenever new train comes just free the platforms which are preoccupied till that time (while loop to remove the prev trains)
//After sorting the arrival and departure arrays
for(int i=0; i
You actually dont need 2 different variables for result and plat_needed bcoz if one train leaves, another might come in its place later and we only care about the maximum platforms used:
int plat_needed = 1, j = 0;
for (int i = 1; i < n; i++) {
if (arr[i]
We can sort it based on arrival time and then use min-heap to get the platform that will be empty at the earliest among the trains that are currently at different platforms. This is easy intuition. Overall complexity will remain same, but the approach explained here is definitely better and optimized. Great help!
That "plz plz plz do subscribe the channel" a nice innocence on the face. I liked that ❤️ and solved the question on my own 😁🎉
What a fabulous solution! Never had the intuition that both arrays can be sorted independently :)
Keep the Face Bro...it feels as if we are discussing it face to face.
Code in Python:
class Solution:
def minimumPlatform(self,n,arr,dep):
arr.sort()
dep.sort()
res, count = 0, 0
a, d = 0, 0
while a < n:
if arr[a]
Add face as it become more interactive. Great explanation. Loved it ❤️
i was also confused so here is my understanding
1. if you are sorting both then
allot platforms by arrival time and then while adding check if any train with departure time before arrival
so if departure time is before it means you have already allotted platform for that
bcz departure for a train always will be more than arrival so
UNDERSTOOD........Thank You So Much for this wonderful video...........🙏🙏🙏🙏🙏🙏
solved all my related problems and queries relating to this question in the vid!!! thankYou
We can solve this question without sorting
int findPlatform(int arr[], int dep[], int n)
{
vector platform(3000,0);
for(int i=0; i
Might be better than striver's code :) (Accepted on all platforms)
T.C : O(2*NLOGN)+O(N)
S.C : O(1)
int findPlatform(int arr[], int dep[], int n)
{
sort(arr,arr+n);
sort(dep,dep+n);
int count=1;
int i=1,j=0;
while(i
Nice One It took some time to understand it but worth it
I am completely just in owe with your teaching style, you're doing an incredible job, the best channel so far to learn and strengthen the concepts, thanks a lot @takeUforward!!!
The intuition was great 🔥... wonderful explanation.
Wonderful Explanation!!!
Damn..that is some intuition!
are you guys able to come with greedy solns optimal one on your own ?? like ive been doing coding from past 5 to 6 months now still these i am not able to come up on my own
More elegant way of writing the same code
int findPlatform(int arr[], int dep[], int n)
{
sort(arr, arr + n);
sort(dep, dep + n);
int totalPlatform = 1, maxPlatform = 0;
int j = 0;
for(int i=1; i
UNDERSTOOD... !!!
Thanks striver for the video... :)
I have a doubt:
You are saying that if a train is arriving at 120, but the first train leaving leaves at 500, so you are saying that how can a train arrive at 120 if the very first train which is leaving leaves at 500, so we need another platform for this train which has to arrive at 120.....right ?
But,
What if the train that is DEPARTING at 500, this train ARRIVED at 499 ?
So, in this case, the train that arrived at 120, we could keep it in the same platform also because may be this train came at 120 and departed at 121........right ?
Edit - Answer which i figured out is - if the "120" arrival train departs at "121", then the sorted departure array's first element will be 121.
But i am still unable to get properly the intuition behind this.
Someone plz explain
Now i get this question. Your way of explaining is very very good.
Thank you, do check out the other problems as well
Can someone tell me the problem:
1 - Sorted the pairs by departure time
2 - Then add departure time in min heap priority queue
3 - Check if arrival is greater than queue top, if it is smaller increase count
Pairs cannot be together. Thats the problem. Just think yourself as a station master, and you just care how many came and how many went. Not when one came and when went
It will not work...
Lets take the example: arr[ ]: [100, 80, 70, 60] and dept[ ]: [700, 350, 90, 150]
In this case, your algo will output 4 but the actual output is 3...
I thought the same algo but performing dry run on some test cases help me understand what's the problem with this algo....i.e. using this we are not keeping track of arrival time of trains on a time frame....which is impacting our overall result.....As striver mentioned in the video we have to keep track of time or we are traversing the time and checking no. of platforms currently occupied....
@@adarshsrivastava7765 Algo is giving correct result for your testcase.
@@takeUforward thanks for station master example...helped me understand better.
holy shitttt! I did the same in my first try (with some modifications) and it worked.
I thought I'd be the only one trying this lmao
MindBlowing and easy to understand intuition striverrrr!!!!!
SHORTER CODE on same idea :
Arrays.sort(arr);
Arrays.sort(dep);
int platform = 1, j = 0;
for(int i = 1; i < n; i++){
if(arr[i]
Should I quit coding and search a different field altogether, I'm failing to crack these machine coding rounds, I'm failing every in Interview and it's been 3 years since I graduated, I lost considerable time learning technologies. Please advise me should I give it up ? I'm now 25 years old fresher
You can prepare for SSC-CGL, it would take a maximum of six months to prepare for the exam but I would like to make it clear you can achieve anything if you study consistently with full dedication.
Ask this question to yourself, then actual struggle starts...
Extraordinary explaination bro it's really clear to understand by your explaination tq bro...
Best content i have ever seen.....thank you so much ..and btw u slayed it
Best explanation for the question. Thanks Striver.
Won't this be better?
public class Solution {
private static void fillArr(int s, int e, int[] arr) {
for(int i=s;i
Thanks a lot. You made me understand it.
This question was asked me in Goldman Sachs interview
all these greedy problems are like that only, follow up ques is meeting rooms 2
your explaination is always very clear . thanks for your tutorials
Bro for initializing platfrom_needed you should declare platform_needed=0 other wise while counting from first platform requirement the code calculate it as 2 instead of one
can't we apply activity selection concept here make a vector pair and then sort it based on arrival time and then compare the starting and ending indexes accordingly
I know we need to maintain a ds to store the dept time and that is gonna take a bit more space just wanted to confirm if this method will work or not
Bhaiya I want to ask one question .
I'm in 4th semester and is it okay if I don't get the best optimised approach and view editorial ?
Yeah its okay
@@takeUforward thank you bhaiya for all this contribution to the community 👍🏻
thank you so much. you explanations are way too good
aree bhaiya , ek hi dil h kitne baar jeetoge....❤❤
These greedy algorithms are simple and crazy 🤩😍. Loving them..
amazing stuff !! subscribed
cannot understand why after a platform is allocated to any train (when arr[i] >dep[j]), the 'i' pointer was not moved to point to the next element of arrival!
Sir please help!
Why does this not work
Main thought : if a train's arrival time is smaller than or equal to least departure time of all trains then one more platform to use else not.
Code:
int findPlatform(int arr[], int dep[], int n) {
int cnt = 0;
set st;
for (int i = 0; i < n; i++) {
if (st.empty()) {
st.insert(dep[i]);
cnt++;
} else {
int leastDepartureTime = *st.begin();
if (arr[i]
This Question is a variation of "N meetings in one room" question, How ?
Here, Instead finding out how many meetings we can arrange in one room we need to find out how many rooms are required if we want to arrange all given meetings.
So, Posting a solution that is based on the solution that is given in "N meetings in one room" question video . Although it's not as efficient as the one given in this video but you can take a look if you wish.
SOLUTION :
class Train {
public int arr, dep;
public Train(int arr, int dep){
this.arr = arr;
this.dep = dep;
}
}
class TrainComparator implements Comparator{
@Override
public int compare(Train t1, Train t2){
// Sorting in Ascending order of arrival time
if(t2.arr minHeap.peek())
minHeap.poll();
minHeap.add(trains.get(i).dep);
platform = Math.max(minHeap.size(), platform);
}
return platform;
}
}
where can i find the doc which is shown in 0:09?
Am i the only one who is not able to understand the intuition of why this approach works or is there anyonr else with me😭
Thanks bro for helping this high school kid out. :)
If i am sorting the two arrays then arrival and departure time for a train gets jumbled. I am confused why we are doing this?
Since arrival < departure always, we just counting how many trains enter and leave throughput the day.
@@takeUforward Why not do the same for Activity Selection Problem ?
can we do it this way:
1) make an array of pairs of starting and departure time of all trains; and sort it(for example, python does this kind of sorting by considering 0th index of pair first, and then 1th index)
2) initialize platforms to be 1, and add departure time of first train in a priority queue.
3) then on next train:
i)if arrival of it is greater than top element in the priorityQueue, remove the top element and add departure time of this train in the priority queue.
ii) if arrival is smaller than top element of the priorityQueue, then increase platforms by 1 and add departure time of this train in the priorityQueue.
repeat step 3 till we reach the end of array
Yes nikhil but we need a extra space for it
I implemented the above code
int findPlatform(int arr[], int dep[], int n)
{
int i,count;
priority_queuepq;
vectorv;
for(i=0;i
Thanks for the intuition. Here's my code for the same
int findPlatform(int start[], int end[], int n)
{
// Your code here
vector v;
for(int i=0;i
Your explaination is best very crystal clear thankyouu
are but.. when we sort both the arrays ..their indexes are not matching for example.for arrival time 50 departure was 550 but after sorting it became 500????? how does this makes sense?
You need how many are in at a time..
So when they are entering that matters, because we know for sure departure will always be after entering.
Hence it makes sense..
@@takeUforward thanks
Solution using min priority queue
int findPlatform(int arr[], int dep[], int n)
{
int i,count;
priority_queuepq;
vectorv;
for(i=0;i
bhaiya..ap bht acha parhate hai..hum avi backtracking kr rehe..apka sde sheet se..pls jaldi jaldi vdo laya..
Thank you, Striver!!!!!
Can I do this ------ i tried with different test cases and got the right answer but WA on gfg.
Please tell me where I made the mistake.
1) put in a multimap, so that both set of values are sorted according to dep_time.
2) have a queue. Insert -1 into it.
3) iterate through the multimap such that
if i->arr_time > q.front() then
{
// this means no need for new platform
q.pop() // old train gone
q.push(i->dep_time) // new train came
}
else {
// this means new platform is required
p++;
//no need to pop as no train to leaving. just put new train
q.push(i->dep_time)
}
4) return p;
Instead of queue using min priority queue
Thanks bro
Loving your videos 😍
bro, I have a doubt. if we are sorting both arrays separately then after sorting it might be possible that at some index the arrival and departure time does not belong to the same train. So suppose in your example, if the train which is leaving at 500 does not even arrive at 50 and came at 120 or so, then how is this solution working in it.. that part is really confusing. Shouldn't we use a custom class "train" and sort it using our own comparator according to arrival and so.
No bro, even if they are not same, it does not matters to me, because i know always arrival of a train is before departure. So i am sure if a train is areiving it will first arrive and then which ever train departs it has for sure arrived and hence is departing, this is the logic here.
@@takeUforward I had the same doubt. Tnx for the clarification
Hello, Im asked to optimize this code. Can someone help? I'm getting this message in terminal "Your program took more time than expected.Expected Time Limit : 1.38sec
Hint : Please optimize your code and submit again."
Your explanation is lit... and very easy for understanding
I know everyone is confused but still is there anyone who understood, and can explain me why are even sorting arr[i] and dep[j] both independently??
God level explanation..
Thank you very much!
Bhaiya face add hii rakhiye
Great video and visualization!
Very beautifully explained!!!
but can we solve it using binary search, its tagged under binary search in gfg
imagine only second platform being occupied
achaai ki bhi seema hoti hai sir ! thank you..😁
Great explanation!!
You can add this solution Link to the SDE sheet page too. Currently, the link to this solution is not there in SDE sheet.
16:22 c++ solution
Thanks bhaia very well explained ❤️
Can you pleasee upload the problem link of all remaining questions.
Superb explanation bro. Thank you!!!
Amazing, Thank you!
we want maximum or minimum platforms?
Awesome as always!
i am so dumbbbb
why is this incorrect. making use of a heap to keep track of the smallest meeting time
class Solution:
def minimumPlatform(self,n,arr,dep):
comb = list(zip(arr, dep))
departureTimes = []
for arrival, departure in comb:
if departureTimes and arrival>departureTimes[0]:
heapq.heappop(departureTimes)
heapq.heappush(departureTimes, departure)
return len(departureTimes)
My O(N) - Time and Space Complexity Solution - Line Sweep Method:
int findPlatform(int a[], int b[], int n)
{
// Your code here
int count[2400]={0};
for(int i=0;i
Thank you so muchc Raj Bhai.
Greta explaination!
1:39 minimum**
understood the aprroach bhayiya but how can we come up with this kind of approach apne aap se like sorting them individually did not even cross my mind while trying
still didn't understand the intution behind this
correction in words it is not maximum number of platform we need to find minimum number of platform.
Understood 💯💯💯
Is anyone knowing the intuition behind this>
He explained the intuition...platforms are vacated when trains leave
God level explanation!!
Please explain the intuition
@@jiosim1377 bro intuition is: no matter which train is leaving or which is arriving because if at initial moment any train arrives then we need a platform or if a train departure then the platform will empty. So that's why we are sorting the arrival and departuring time.
Example-
0900 0910 1100
0920 0945 1130
So here as you can see I have sorted both the times so now--
first train will leave at 09:20 and next train is coming at 09:10 (before the first train goes) so we need one more platform.
But if after leaving of one train next will arrive that means first platform will get empty.
@@jiosim1377 go through the video once, you will understand more clearly. ❤️
bro please provide the links of all problems in the sde sheet . We are not able to find all the problems on leet code and adding links makes our work easier . Thanks in advance :)
Its either at gfg or leetcode, just google the problem names!!
@@takeUforward thanks...how do i contact you if i have any doubts ?
@@nishanthmolleti188 Instagram or put the comment, I usually reply to a comment where someone is asking something
i tried a different approach...this also works........
// You are using Java
import java.util.*;
class Activity{
int start,end;
Activity(int start,int end){
this.end=end;
this.start=start;
}
}
class MyComparator implements Comparator{
public int compare(Activity a1,Activity a2){
return a1.end-a2.end;
}
}
class Main{
public static void main(String args[]){
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int count = 0;
int start[] = new int [n];
int end[] = new int [n];
List obj = new ArrayList();
List temp = new ArrayList();
for(int i=0;i
Very well explaination!
awesome explaination it helps lot of students
Can someone explain why sorting the two arrays didn't affect the answer?
Because we only care as a station. Kb aa rahe and kab jaa rhe matter krta. Ovio h ki jaane wla time hmsha aane wle k bd hi aaega
@@takeUforward Okay bhaiya, aa gya smjh, Thanks!
And you are doing a wonderful job I love your channel!
Amazing explanation!
can't we use kadane's in this?