Suppose there is only one platform and N number of trains. So at any point of time only 1 train will stay in platform. N time intervals (arrival and departure) are given which represent the timing duration of N trains.You have to find what is minimum number of trains that have to be postponed such that no collision take place.
Any ideas how to do this one? DP? Any help is appreciated!
what is meant by postponing a train? Are we allowed to change the arrival and departure times of such train?
sort(all intervals on basis of departure time) F[idx][last] = number of trains from first idx trains through platform without collision
F[idx][last] = F[idx+1][idx] if interval idx and last trains do not collide
or F[idx+1][last] if we skip this trains either due to collision or we just skip it
= min(of both cases)
answer = N — (max(F[idx+1][idx]) for all idx)
there is a greedy approach to :D think about it
Suppose we have two trains. One arrives at time 1, and leaves at 1000. Another one arrives at 800 and leaves at 801.
Which one do you choose to postpone? I think It's better strategy to postpone the train that arrives at 800, this way the third train (if exists) can arrive as soon as 1001. Am I correct?