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)
@@ababhimanyu806 N rooms u were searching for nonoverlapping intervals so u need to sort by end time , but here u are looking for overlapping intervals so u will sort by the start time
@@ababhimanyu806 you can do it but while keeping prev array for the previous interval you need to use a heap , to check the overlapping intervals simulatenously, i did it that way and it worked
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.
This what I managed to do without watching Striver's video. Let's see how off I am and where all I make improvements. class Solution{ /* KeyPoints(KP):- 1) Arr and Dep int arrays are given. 2) No train must be waiting. 3) Minimize the no of platforms taken. 4) Arr[i] != Dep[i] but Arr[j] may be equal to Dep[i] for i!=j. 5) Even if Dep[i] == Arr[j] for i!=j, same platform cannot be used. Observations(OB):- 1) Makes sense to sort the array of trains by their departure time. 2) If there is some overlap between Arr and Dep of 2 different trains, new platform is needed due to KP5. 3) If we say during time t = Arr[i], no of trains in wait is increased by one then we can say we t = Dep[i] + 1, no of. trains in wait is decreased by one. 4) The OB3 implies we can use a sweep-line algorithm with prefix sum to know at time 't' how many trains are in wait. 5) OB4 also implies that if we just find the max value in the prefix sums array, we can know how many platforms are needed at most as if we say 3 platforms are needed at most for day, then at no point in the day would we need more than 3. Algorithm Analysis:- -> First we sort a custom trains array, hence T = O(nlogn) & S = O(n). -> We create an array to store no of trains in wait during time 't'. This means an array of size (2400, ie no of hours in one day) ie S = O(1). -> Iterate through all train objects, incrementing Time[arr[i]] by 1 and decrementing Time[dep[i]] by 1. -> Traverse from t = 0 to t = 2359 and modify the Time array to a prefix array. -> Return the max value from Time array. Hence, T = O(nlogn) , S = O(n). */ public: //Function to find the minimum number of platforms required at the //railway station such that no train waits. int findPlatform(int arr[], int dep[], int n) { // Your code here vector trains; vector trainsWaiting(2401); for(int i = 0; i < n; ++i){ trains.push_back({arr[i], dep[i]}); } sort(trains.begin(), trains.end(), [](vector& a, vector& b){ return a[1] < b[1]; }); for(auto &train : trains){ trainsWaiting[train[0]]++; trainsWaiting[train[1] + 1]--; } for(int t = 1; t < 2401; t++){ trainsWaiting[t] += trainsWaiting[t-1]; } return *max_element(trainsWaiting.begin(), trainsWaiting.end()); } };
A very easy approach keep a vector of size "24*60+1" size and for every train keep check how many trains are present at that minute of time. Return the maximum of the vector. Easy and intuitive O(n) approach
Do you mean to say that for every train you will increment +1 from arrival minute to departure minute??? If we follow this approach The worst case time and space complexity: Space: 24-60 + 1 = 1441 For every train you will iterate from arrival_min to depart_min and do +1. IN worst case you might have to iterate complete array i.e. 1441. SO for n trains TC = 1441 * n as per problem n can be max 50000 SO TC = 1441 * n = 7.2 * 10^7 IS this not slow?
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
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.😊😊🙂🙂
class Solution { public: // Function to find the minimum number of platforms required at the // railway station such that no train waits. int findPlatform(vector& arr, vector& dep) { // Your code here sort(arr.begin(), arr.end()); sort(dep.begin(), dep.end()); int i = 0, j = 0; int n = arr.size(); int max_count = 0; int required = 0; while(i < n && j < n){ if(arr[i]
// Comparator function to ensure that departures are processed before arrivals when times are equal static bool comp(pair val1, pair val2) { if (val1.first == val2.first) { // If times are the same, give priority to departure return val1.second < val2.second; } return val1.first < val2.first; } int findPlatform(int arr[], int dep[], int n) { vector clockArray; // Create pairs of (time, 'A' or 'D') for all arrival and departure times for(int i = 0; i < n; i++) { clockArray.push_back({arr[i], 'A'}); // 'A' for arrival clockArray.push_back({dep[i], 'D'}); // 'D' for departure } // Sort the events by time, with departures before arrivals if times are equal sort(clockArray.begin(), clockArray.end(), comp); int MaxCount = 0; int count = 0; // Traverse the sorted events for(int i = 0; i < 2 * n; i++) { if(clockArray[i].second == 'A') { // Train arrives, increase the platform count count++; } else { // Train departs, decrease the platform count count--; } // Update the maximum number of platforms needed MaxCount = max(MaxCount, count); } return MaxCount; }
This problem is exactly similar to (CSES - Restaurant Customers) ... must check it I'll suggest ! Another approach : (nlogn) -> Take arrival and depart times in a pair of vector and sort on the basis of depart time. Now you can use a multiset named platforms (storing the depart time of last train on each platform) initially storing only one element {-1}, Now iterate from 0 to n-1 and use lower_bound function to find suitable platform for each train (if available else add new platform) ... finally return size of this multiset platforms.
The brutefore will give wrong answer take example : (1,7) ,(2,3),(4,5) no of overlaps for (1,7) will be 2 but (2,3) and (4,5) are not overlapping hence can be on same platform so ans wont be 3 it would be 2. check code for this input: int arr[]={900,945,955,1100,1500,1800}; int dep[]={920,1200,1000,1150,1900,2000};
There is a problem with the brute force approach , change the 3rd index arrival time from 1100 to 1140 in the given example and you will see the approach will still give 3 as answer but it's correct answer is 2. From there you can figure out where the problem is in the approach.
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)
class Solution { public: // Function to find the minimum number of platforms required at the // railway station such that no train waits. int findPlatform(vector& arr, vector& dep) { int n = arr.size(); int platform = 1; sort(arr.begin(), arr.end()); sort(dep.begin(), dep.end()); int maxplatform = 1; int i = 1; int j= 0; while(i
O(n) code int findPlatform(int arr[], int dep[], int n) { // Arrivals and Departures in sorted order vector arrival(2401, 0); vector departure(2401, 0); for(int i=0; i
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 .
Asaan bhasha Mai, We sorted acc to time, The clock is ticking!! We find the train which arrived, if arrived then platform++ , if depart then platform --,
I don't know why my strategy is not working. My strategy is to maximize the number of trains that can fit on a single platform by first sorting the trains based on their departure times. After sorting, I pick the maximum number of non-overlapping trains, mark them as visited, and assign them to one platform. I then repeat this process for the remaining unvisited trains, adding a new platform each time until all trains are assigned. This is not giving the right answer. Does anyone know what could be a potential issue with this? I think my approach should be optimal because, at each iteration, I'm trying to fit the maximum number of trains on the platform and repeat the process for the remaining.
Hey guyz those looking for a TC:- O( N ) solution and SC:- O( 2365 ~ 1 ) this works vector vect(2365, 0); int ans = 0; int n = arr.size(); for(int i=0; i
JAVA SOLUTION 👇 class Solution { static int findPlatform(int arr[], int dep[], int n) { Arrays.sort(arr); Arrays.sort(dep); int neededPlatforms = 1; int maxPlatforms = 1; int i=1, j=0; while(i
class Solution: def minimumPlatform(self,n,arr,dep): # code here plat=[] mixarr=[[int(arr[i]),int(dep[i])] for i in range(len(arr))] mixarr=sorted(mixarr,key=lambda x:x[1]) for a,d in mixarr: assignedtosomeplat=False for i in range(len(plat)): if plat[i]
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
Thanks Striver for all your efforts .But Brute Force approach is Incorrect. The correct brute force code is below: public int findPlatform(int[] arr, int[] dep, int n) { int maxPlatforms = 0; // Iterate through each train's arrival time for (int i = 0; i < n; i++) { int count = 0; // Check for each train if it overlaps with the train i for (int j = 0; j < n; j++) { //checking arr[j]
I came up with my original solution in just 30 minutes , its interesting but bad in TC , TC : O(n) + O(N Log N) + O(N^2) SC : O(2N) class Solution { public:
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)
@@ababhimanyu806 N rooms u were searching for nonoverlapping intervals so u need to sort by end time , but here u are looking for overlapping intervals so u will sort by the start time
@@ababhimanyu806 you can do it but while keeping prev array for the previous interval you need to use a heap , to check the overlapping intervals simulatenously, i did it that way and it worked
@@jotsinghbindra8317 but we can keep the count of things that are not fitting to our time interval that no of diff platform we require + 1
This explanation is so much better and intuitive than the previous video!! Thanks Striver
Waiting for Heaps and strings playlist 🙌👍
See Aditya Verma playlist
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
we have to sort arrival time because all testcases don't have sorting so to pass all testcases we have to sort arrival time also
This what I managed to do without watching Striver's video. Let's see how off I am and where all I make improvements.
class Solution{
/*
KeyPoints(KP):-
1) Arr and Dep int arrays are given.
2) No train must be waiting.
3) Minimize the no of platforms taken.
4) Arr[i] != Dep[i] but Arr[j] may be equal to Dep[i] for i!=j.
5) Even if Dep[i] == Arr[j] for i!=j, same platform cannot be used.
Observations(OB):-
1) Makes sense to sort the array of trains by their departure time.
2) If there is some overlap between Arr and Dep of 2 different trains,
new platform is needed due to KP5.
3) If we say during time t = Arr[i], no of trains in wait is increased by
one then we can say we t = Dep[i] + 1, no of. trains in wait is decreased
by one.
4) The OB3 implies we can use a sweep-line algorithm with prefix sum
to know at time 't' how many trains are in wait.
5) OB4 also implies that if we just find the max value in the prefix sums
array, we can know how many platforms are needed at most as if we say
3 platforms are needed at most for day, then at no point in the day
would we need more than 3.
Algorithm Analysis:-
-> First we sort a custom trains array, hence T = O(nlogn) & S = O(n).
-> We create an array to store no of trains in wait during time 't'. This means an
array of size (2400, ie no of hours in one day) ie S = O(1).
-> Iterate through all train objects, incrementing Time[arr[i]] by 1 and
decrementing Time[dep[i]] by 1.
-> Traverse from t = 0 to t = 2359 and modify the Time array to a prefix array.
-> Return the max value from Time array.
Hence, T = O(nlogn) , S = O(n).
*/
public:
//Function to find the minimum number of platforms required at the
//railway station such that no train waits.
int findPlatform(int arr[], int dep[], int n)
{
// Your code here
vector trains;
vector trainsWaiting(2401);
for(int i = 0; i < n; ++i){
trains.push_back({arr[i], dep[i]});
}
sort(trains.begin(), trains.end(),
[](vector& a, vector& b){
return a[1] < b[1];
});
for(auto &train : trains){
trainsWaiting[train[0]]++;
trainsWaiting[train[1] + 1]--;
}
for(int t = 1; t < 2401; t++){
trainsWaiting[t] += trainsWaiting[t-1];
}
return *max_element(trainsWaiting.begin(), trainsWaiting.end());
}
};
A very easy approach keep a vector of size "24*60+1" size and for every train keep check how many trains are present at that minute of time. Return the maximum of the vector. Easy and intuitive O(n) approach
Do you mean to say that for every train you will increment +1 from arrival minute to departure minute???
If we follow this approach
The worst case time and space complexity:
Space: 24-60 + 1 = 1441
For every train you will iterate from arrival_min to depart_min and do +1.
IN worst case you might have to iterate complete array i.e. 1441. SO for n trains TC = 1441 * n
as per problem n can be max 50000
SO TC = 1441 * n = 7.2 * 10^7
IS this not slow?
@@Bunny-kn4hi Yeah. Not optimal
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!!
can u please explain why this approach failed..? what went wrong in the thought process?
great explanation ever😍
You made this question looks so easy. Wow!!
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.😊😊🙂🙂
Thank you 😊
arrival depature count approach is excellent
class Solution {
public:
// Function to find the minimum number of platforms required at the
// railway station such that no train waits.
int findPlatform(vector& arr, vector& dep) {
// Your code here
sort(arr.begin(), arr.end());
sort(dep.begin(), dep.end());
int i = 0, j = 0;
int n = arr.size();
int max_count = 0;
int required = 0;
while(i < n && j < n){
if(arr[i]
// Comparator function to ensure that departures are processed before arrivals when times are equal
static bool comp(pair val1, pair val2) {
if (val1.first == val2.first) {
// If times are the same, give priority to departure
return val1.second < val2.second;
}
return val1.first < val2.first;
}
int findPlatform(int arr[], int dep[], int n) {
vector clockArray;
// Create pairs of (time, 'A' or 'D') for all arrival and departure times
for(int i = 0; i < n; i++) {
clockArray.push_back({arr[i], 'A'}); // 'A' for arrival
clockArray.push_back({dep[i], 'D'}); // 'D' for departure
}
// Sort the events by time, with departures before arrivals if times are equal
sort(clockArray.begin(), clockArray.end(), comp);
int MaxCount = 0;
int count = 0;
// Traverse the sorted events
for(int i = 0; i < 2 * n; i++) {
if(clockArray[i].second == 'A') {
// Train arrives, increase the platform count
count++;
} else {
// Train departs, decrease the platform count
count--;
}
// Update the maximum number of platforms needed
MaxCount = max(MaxCount, count);
}
return MaxCount;
}
This problem is exactly similar to (CSES - Restaurant Customers) ... must check it I'll suggest !
Another approach : (nlogn) ->
Take arrival and depart times in a pair of vector and sort on the basis of depart time. Now you can use a multiset named platforms (storing the depart time of last train on each platform) initially storing only one element {-1}, Now iterate from 0 to n-1 and use lower_bound function to find suitable platform for each train (if available else add new platform) ... finally return size of this multiset platforms.
beautiful intuition !
Sort by time, but if times are the same, prioritize 'D' (departure) over 'A' (arrival), If using time lapse approach
why
This is one of the finest solution, i have seen striver. It is really waoo.
Good job, keep sharing the learning with us.
Sir please start making videos on strings and stacks
you standing at the railway station and counting was brilliant
Ur explanation has become good as compared to ur previous video on the same question ,a lot better
The brutefore will give wrong answer
take example : (1,7) ,(2,3),(4,5)
no of overlaps for (1,7) will be 2 but (2,3) and (4,5) are not overlapping hence can be on same platform so ans wont be 3 it would be 2.
check code for this input:
int arr[]={900,945,955,1100,1500,1800};
int dep[]={920,1200,1000,1150,1900,2000};
Fails for below as well
900 1000 1100
1200 1010 1150
i think prefix sum is a good approach.
Really brilliant explanation
We can easily apply sweep line algorithm👍
yes, waiting for Heaps and strings playlist
Thank you for great Explaination.
There is a problem with the brute force approach , change the 3rd index arrival time from 1100 to 1140 in the given example and you will see the approach will still give 3 as answer but it's correct answer is 2. From there you can figure out where the problem is in the approach.
Waiting for string and stack queue videos more
understood, thanks for the perfect explanation
I understood the brute. Max overlaps = Min platforms
This approach is also known as Line Sweep Algorithm and it can be used to solve many interval related problems.
great sir
eagerly waiting for heap and string playlist
Understood! As the time goes by 😋
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)
Bhaiya strings and heaps ki playlist kab la rhe
class Solution {
public:
// Function to find the minimum number of platforms required at the
// railway station such that no train waits.
int findPlatform(vector& arr, vector& dep) {
int n = arr.size();
int platform = 1;
sort(arr.begin(), arr.end());
sort(dep.begin(), dep.end());
int maxplatform = 1;
int i = 1;
int j= 0;
while(i
excellent
Thanks
UNDERSTOOD;
genius!
understood
Pls continue this
beautiful
O(n) code
int findPlatform(int arr[], int dep[], int n)
{
// Arrivals and Departures in sorted order
vector arrival(2401, 0);
vector departure(2401, 0);
for(int i=0; i
why sliding window after sorting is giving wrong answer for this question?
In the basic approach why are we taking the maxCount? Aren't we required to find the minimum no of platforms required. Can any one please explain
bruteforce is not at all intitutive but ya its a good concept
I know by sorting we can get the answer but how come we change the train departure timings by sorting. That's not possible in real life.
Understood
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
Asaan bhasha Mai,
We sorted acc to time,
The clock is ticking!! We find the train which arrived, if arrived then platform++ , if depart then platform --,
T.C O(N) and S.C O(1)
class Solution{
public:
int findPlatform(int nums[], int dep[], int n)
{
vector arr(2362);
for(int i = 0; i < n; i++){
arr[nums[i]] += 1;
arr[dep[i] + 1] += -1;
}
int ans = arr[0];
for(int i = 1; i < 2362; i++){
arr[i] += arr[i - 1];
ans = max(ans , arr[i]);
}
return ans;
}
};
noice understood
I don't know why my strategy is not working.
My strategy is to maximize the number of trains that can fit on a single platform by first sorting the trains based on their departure times. After sorting, I pick the maximum number of non-overlapping trains, mark them as visited, and assign them to one platform. I then repeat this process for the remaining unvisited trains, adding a new platform each time until all trains are assigned.
This is not giving the right answer. Does anyone know what could be a potential issue with this?
I think my approach should be optimal because, at each iteration, I'm trying to fit the maximum number of trains on the platform and repeat the process for the remaining.
solved using min priority queue anyone else
yeah
Hey guyz those looking for a TC:- O( N ) solution and SC:- O( 2365 ~ 1 ) this works
vector vect(2365, 0);
int ans = 0;
int n = arr.size();
for(int i=0; i
JAVA SOLUTION 👇
class Solution
{
static int findPlatform(int arr[], int dep[], int n)
{
Arrays.sort(arr);
Arrays.sort(dep);
int neededPlatforms = 1;
int maxPlatforms = 1;
int i=1, j=0;
while(i
Hi bhaiya, how are you!
3
0930 1010 1110
1210 1100 1200
Your Output:
3
Expected Output:
2
according to your brute force method this code will not work
class Solution:
def minimumPlatform(self,n,arr,dep):
# code here
plat=[]
mixarr=[[int(arr[i]),int(dep[i])] for i in range(len(arr))]
mixarr=sorted(mixarr,key=lambda x:x[1])
for a,d in mixarr:
assignedtosomeplat=False
for i in range(len(plat)):
if plat[i]
iI solved this question on own using arrival time see this
class Solution{
public:
static bool comparator(vectora,vectorb)
{
if(a[0]
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
Livestreaming platform
Thanks Striver for all your efforts .But Brute Force approach is Incorrect. The correct brute force code is below:
public int findPlatform(int[] arr, int[] dep, int n)
{
int maxPlatforms = 0;
// Iterate through each train's arrival time
for (int i = 0; i < n; i++) {
int count = 0;
// Check for each train if it overlaps with the train i
for (int j = 0; j < n; j++) {
//checking arr[j]
will it work for this : (1100 ,1800), (1300,1400), (1500,1600) ? the answer is 2 but your code will give 3
God takes birth on earth in the form of striver.
This is a weird question.
wrong bruteforce , wrong logic of optimal solution
hii sir
First comment 😀
I came up with my original solution in just 30 minutes , its interesting but bad in TC ,
TC : O(n) + O(N Log N) + O(N^2)
SC : O(2N)
class Solution {
public:
static bool comp(vector &a , vector &b){
return a[0] < b[0];
}
int findPlatform(vector& arr, vector& dep) {
vector p;
for(int i = 0; i < arr.size(); i++){
p.push_back({arr[i],dep[i]});
}
sort(p.begin(),p.end(),comp);
vector freetime;
freetime.push_back(p[0][1]); //first train dep time
for(int i = 1 ; i < p.size(); i++){
bool isAvail = false;
for(int j = 0; j < freetime.size(); j++){
if(p[i][0] > freetime[j]){
isAvail = true;
freetime[j] = p[i][1];
break;
}
}
if(!isAvail) freetime.push_back(p[i][1]);
}
return freetime.size();
}
};
understood
Understood