Interview Scheduling: Maximum Simultaneous Interviews

You are given n interview requests and m interviewers. Each interview i is characterized by a start time \(s_i\) and an end time \(e_i\), where \(s_i \le e_i\). Each interviewer can conduct at most one interview at any given time. In other words, the same interviewer cannot handle overlapping interviews.

Your task is to select a subset of these interviews to schedule such that the interviews assigned to each interviewer do not overlap. The goal is to maximize the total number of interviews being conducted simultaneously by the interviewers. Note that even though interviews may be arranged sequentially on one interviewer, the maximum number of interviews that can occur concurrently cannot exceed m. Formally, if you can schedule a total of \(C\) interviews, the result is \(\min(C, m)\).

Input/Output Note: All input is read from stdin and output is written to stdout.

inputFormat

The first line contains two integers n and m separated by a space, representing the number of interviews and the number of interviewers, respectively. Each of the following n lines contains two space-separated integers \(s_i\) and \(e_i\) representing the start time and end time of an interview.

It is guaranteed that \(s_i \le e_i\) for all interviews.

outputFormat

Output a single integer — the maximum number of interviews that can be conducted simultaneously by the m interviewers, calculated as \(\min(C, m)\), where C is the total number of scheduled interviews using a greedy allocation strategy.

3 2
1 5
2 6
6 10

2