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!
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
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
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.
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
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!
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
@@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.
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]
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
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
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
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
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!!!
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....
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; } }
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.
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
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
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
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
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;
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
I understood the algorithm very good explanation, but why do we need to sort the departure and arrival doesn't the arrival and departure change for trains or how do we assume that we can sort it in the first place???
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]
If you are allowed to use extra space of O(2401) you can achieve a time complexity of O(N+2401) . The reason we could do this is because maximum value on time could be 2359, but this kind of shouldn't be considered when input goes to 10^9, if that happens you could use the same logic but with map data structure: int findPlatform(int arr[], int dep[], int n) { // Your code here int dp[2401]={0}; for(int i=0;i
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!
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..
Thank you soo much bhya for making videos in your hard time also 🙏🙏🤕, you are like big brother for us, thank you soo soo much. And to see you in video and understand the algorithm is like your live class 💓🤩🤩🤩, keep it in all your videos 💥💯💯💥
Hello sir,can you please tell why my approach fails 1) sort the pair according to arrival time 2) In a set insert the departure time of first train 3) Now for others check in the set whether there is a train with departure time less than the arrival time of current train . 4) If true then erase it and insert the new departure time 5)else insert the new departure time 6) return the size of the set
I have also used the same logic but used vector instead of set and it is working. int findPlatform(int arr[], int dep[], int n) { vector schedule; for(int i=0;i
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
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.
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."
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;
Can anyone please tell me what is wrong with my approach along with the testcase ? Here is my code int findPlatform(int arr[], int dep[], int n) { vector timings; for(int i=0; i
Bro... please make a vedio on STL in C++ .... please....I am following your channel when you post a vedio....very helpful people like me in tier 3 colleges...so please consider this a request.....and when you are make a vedio on STL bro.... thanks thanks a lot🙏👍👍👍👍👍
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
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
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.
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.
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
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!
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.
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]
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
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]
That "plz plz plz do subscribe the channel" a nice innocence on the face. I liked that ❤️ and solved the question on my own 😁🎉
Keep the Face Bro...it feels as if we are discussing it face to face.
We can solve this question without sorting
int findPlatform(int arr[], int dep[], int n)
{
vector platform(3000,0);
for(int i=0; i
What a fabulous solution! Never had the intuition that both arrays can be sorted independently :)
Add face as it become more interactive. Great explanation. Loved it ❤️
UNDERSTOOD........Thank You So Much for this wonderful video...........🙏🙏🙏🙏🙏🙏
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
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
Damn..that is some intuition!
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
Won't this be better?
public class Solution {
private static void fillArr(int s, int e, int[] arr) {
for(int i=s;i
The intuition was great 🔥... wonderful explanation.
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!!!
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
solved all my related problems and queries relating to this question in the vid!!! thankYou
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]
Now i get this question. Your way of explaining is very very good.
Thank you, do check out the other problems as well
This question was asked me in Goldman Sachs interview
aree bhaiya , ek hi dil h kitne baar jeetoge....❤❤
MindBlowing and easy to understand intuition striverrrr!!!!!
UNDERSTOOD... !!!
Thanks striver for the video... :)
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;
}
}
Solution using min priority queue
int findPlatform(int arr[], int dep[], int n)
{
int i,count;
priority_queuepq;
vectorv;
for(i=0;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...
These greedy algorithms are simple and crazy 🤩😍. Loving them..
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
Best explanation for the question. Thanks Striver.
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
Wonderful Explanation!!!
all these greedy problems are like that only, follow up ques is meeting rooms 2
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
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
achaai ki bhi seema hoti hai sir ! thank you..😁
Best content i have ever seen.....thank you so much ..and btw u slayed it
Thanks bro for helping this high school kid out. :)
your explaination is always very clear . thanks for your tutorials
Extraordinary explaination bro it's really clear to understand by your explaination tq bro...
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 👍🏻
where can i find the doc which is shown in 0:09?
i am so dumbbbb
Thanks a lot. You made me understand it.
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
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
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 ?
correction in words it is not maximum number of platform we need to find minimum number of platform.
I understood the algorithm very good explanation, but why do we need to sort the departure and arrival doesn't the arrival and departure change for trains or how do we assume that we can sort it in the first place???
Train will come then only it will go naa, by that thought process!
Your explaination is best very crystal clear thankyouu
thank you so much. you explanations are way too good
Bhaiya face add hii rakhiye
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]
If you are allowed to use extra space of O(2401) you can achieve a time complexity of O(N+2401) .
The reason we could do this is because maximum value on time could be 2359, but this kind of shouldn't be considered when input goes to 10^9, if that happens you could use the same logic but with map data structure:
int findPlatform(int arr[], int dep[], int n)
{
// Your code here
int dp[2401]={0};
for(int i=0;i
Your explanation is lit... and very easy for understanding
God level explanation..
Thank you very much!
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??
bhaiya..ap bht acha parhate hai..hum avi backtracking kr rehe..apka sde sheet se..pls jaldi jaldi vdo laya..
Thank you, Striver!!!!!
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!
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
1:39 minimum**
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😭
Thank you soo much bhya for making videos in your hard time also 🙏🙏🤕, you are like big brother for us, thank you soo soo much.
And to see you in video and understand the algorithm is like your live class 💓🤩🤩🤩, keep it in all your videos 💥💯💯💥
16:22 c++ solution
imagine only second platform being occupied
amazing stuff !! subscribed
Thanks bro
Loving your videos 😍
Thanks bhaia very well explained ❤️
Can you pleasee upload the problem link of all remaining questions.
Hello sir,can you please tell why my approach fails
1) sort the pair according to arrival time
2) In a set insert the departure time of first train
3) Now for others check in the set whether there is a train with departure time less than the arrival time of current train .
4) If true then erase it and insert the new departure time
5)else insert the new departure time
6) return the size of the set
I also thought the same. Please let me know if you will find out why this approach is incorrect ?
I built the same logic too... plz let me know if you've found the error.
I have also used the same logic but used vector instead of set and it is working.
int findPlatform(int arr[], int dep[], int n)
{
vector schedule;
for(int i=0;i
but can we solve it using binary search, its tagged under binary search in gfg
You can add this solution Link to the SDE sheet page too. Currently, the link to this solution is not there in SDE sheet.
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
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
Very beautifully explained!!!
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."
Superb explanation bro. Thank you!!!
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
Can anyone please tell me what is wrong with my approach along with the testcase ? Here is my code
int findPlatform(int arr[], int dep[], int n)
{
vector timings;
for(int i=0; i
awesome explaination it helps lot of students
Bro... please make a vedio on STL in C++ .... please....I am following your channel when you post a vedio....very helpful people like me in tier 3 colleges...so please consider this a request.....and when you are make a vedio on STL bro.... thanks thanks a lot🙏👍👍👍👍👍
There is already one. Check channel’s opening page!!
@@takeUforward got it👍👍👍👍👍👍
Is anyone knowing the intuition behind this>
He explained the intuition...platforms are vacated when trains leave
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!
Great video and visualization!
Thank you so muchc Raj Bhai.
why in n meetings qques we sort arraylist but here we sort both arrray differently
video for question is not clear...
Why merging overlapping intervals doesn’t work ?
striver is a savior.
Amazing, Thank you!
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
Loved it, and striver please include your video it's helps