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.
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
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
@@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
@@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)
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.😊😊🙂🙂
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)
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
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 .
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
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.
nice explanation man, really helpful
Waiting for Heaps and strings playlist 🙌👍
See Aditya Verma playlist
This is one of the finest solution, i have seen striver. It is really waoo.
Good job, keep sharing the learning with us.
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
exactly the same doubt thanks for pointing it out
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
great observation skills
Exactly what Im thinking about!!
You made this question looks so easy. Wow!!
This explanation is so much better and intuitive than the previous video!! Thanks Striver
Sir please start making videos on strings and stacks
Waiting for string and stack queue videos more
Ur explanation has become good as compared to ur previous video on the same question ,a lot better
yes, waiting for Heaps and strings playlist
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
but nested for loop causes O(N^2)
@@drishtiambastha3141 The nested for loop can run upto max 2360 times for every ith element which makes TC = O(N * 2360) ~= O(N)
But log(n) value is lesser than the 2360,
@@thoughtsofkrishna8963 no its not. O(2360) ~= O(1) and O(log n) > O(1)
@@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
This is cleverly crafted problem of meeting rooms.
why we cant use that approach in this question?
@@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)
eagerly waiting for heap and string playlist
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.😊😊🙂🙂
Pls continue this
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)
Understood
why sliding window after sorting is giving wrong answer for this question?
Hi bhaiya, how are you!
Livestreaming platform
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
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 .
I too had this question. There is more dicussion in the older version of this problem that Striver uploaded few years ago.
@@smarajitadak6681 very nice explanation bro, tysm
First comment 😀
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