Maximum Non-Overlapping Workshops Scheduling

You are given n workshops and m available rooms. Each workshop is represented by its start time s and end time e. Your task is to schedule as many workshops as possible such that no two workshops in the same room overlap. Two workshops \( (s_1, e_1) \) and \( (s_2, e_2) \) do not overlap if \( s_2 \geq e_1 \) when \( e_1 \) is the finish time of the earlier workshop.

A greedy strategy that sorts workshops by their ending times is effective for this problem. Formally, for a workshop \( (s,e) \), it can be scheduled in a room if:

[ s \geq \text{last_end_time} ]

Determine the maximum number of workshops that can be scheduled given m rooms.

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and m — the number of workshops and the number of available rooms respectively. The following n lines each contain two integers s and e, representing the start and end times of a workshop.

outputFormat

Output a single integer, the maximum number of workshops that can be scheduled across the m rooms, printed to standard output (stdout).

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

4