Maximum Train Scheduling on Limited Tracks

You are given N trains, each with an arrival time and a departure time, and a station with T available tracks. Your task is to determine the maximum number of trains that can be accommodated at the station under the constraint that at most T trains can be present at the station simultaneously.

A train is considered accommodated if it arrives and departs without conflicting with others on the same track. When a train arrives, if there is a track that becomes available (i.e. its train has departed such that \(\min\{d\} < a\)), then the arriving train can be assigned to that track. Otherwise, if the number of trains currently occupying tracks is less than T, the train can be assigned a free track.

This problem can be effectively solved with a greedy approach using a min-heap data structure to track the departure times of trains currently on the tracks. The algorithm sorts the trains by their arrival times, then iteratively assigns each train to a track (if available) by removing any train from the heap whose departure time is less than the current train's arrival time.

inputFormat

The input is given via stdin and has the following format:

N T
arrival_1 departure_1
arrival_2 departure_2
... 
arrival_N departure_N

Here, N is the number of trains and T is the number of available tracks. Each of the next N lines contains two integers representing the arrival and departure times of a train.

outputFormat

The output, printed to stdout, is a single integer representing the maximum number of trains that can be accommodated at the station given the track constraints.

5 2
1 4
2 5
3 6
7 8
5 9

4