Minimum number of trains to be postponed to avoid any overlap in schedule

Given n time intervals for which n trains will occupy a station, find minimum number of trains to be postponed to avoid any overlap in schedule.

Finding the minimum number of trains to postpone will be same as finding the maximum number of non overlapping intervals of trains that can be allowed and then, your answer will be n-max. Let A[i] denote the maximum number of trains that can be allowed in the first ‘i’ units of time, process the intervals in the increasing order of ending times. For every interval, say, [start,end], you will see if you can do better than the existing solution for the interval [0,end] ie. ‘end’ units of time:

A[end] = max(A[end],1+a[start-1])

The answer will be the maximum of all values present in the array A[], and your answer will be n-max. If the numbers representing the intervals are large, you can sort them and map them to numbers starting from 1.

//