Overview

This is a problem of finding the maximum number of meetings that can be selected from \(N\) meetings such that their time intervals do not overlap with each other. This is a well-known greedy algorithm problem called the “Interval Scheduling Problem.”

Analysis

Naive Approach and Its Issues

One could consider trying all combinations of meetings to find the largest subset of non-overlapping meetings. However, the number of subsets of \(N\) meetings is \(2^N\), and since \(N\) can be up to \(2 \times 10^5\), this approach is far too slow.

Key Insight: Prioritize Meetings with Earlier End Times

Let’s think about this intuitively. If we can “free up the meeting room as early as possible,” we increase the chances of fitting more meetings afterward.

For example, consider the following 3 meetings:

• First, select meeting A, which has the earliest end time (end time 3).
• Next, look for meetings that start at or after time 3. Meeting C (start time 3) can be selected.
• Result: The maximum is 2 meetings, A and C.

If we had selected meeting B first, none of the remaining meetings could be selected, leaving us with only 1 meeting. It is known that greedily selecting meetings in order of earliest end time yields the optimal solution.

Algorithm

This problem is known as the Interval Scheduling Problem, and the following greedy algorithm provides the optimal solution.

1. Sort all meetings in ascending order of end time \(R_i\) (if end times are the same, ascending order of start time is fine).
2. Initialize a variable last_end (the end time of the last selected meeting) to \(-1\).
3. Iterate through the meetings in sorted order. If the start time \(L_i \geq\) last_end:
   • Select that meeting and increment count by \(1\).
   • Update last_end to \(R_i\).
4. The final count is the answer.

Why is this correct?
By selecting meetings with earlier end times, we maximize the remaining available time. This greedy choice does not narrow down future options, which is guaranteed by an exchange argument (a proof that swapping a non-selected meeting with a selected one never results in a worse outcome).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (to store the list of meetings)

Implementation Notes

• By using tuples (R_i, L_i) as the sort key, Python’s standard sort naturally sorts in ascending order of end time. In the code, by writing meetings.append((r, l)) to make the first element of the tuple the end time, sorting is completed with just meetings.sort().

• The condition for meetings not to overlap is \(L_i \geq\) last_end (the start time is at or after the end time of the previous meeting). As stated in the problem, when an end time and a start time coincide (\(R_i = L_j\)), the meetings do not overlap, so the comparison should use >= (including equality).

• Reading all input at once with sys.stdin.read() and splitting with split() is faster than calling input() repeatedly when \(N\) is large.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    meetings = []
    idx = 1
    for i in range(n):
        l = int(input_data[idx])
        r = int(input_data[idx + 1])
        meetings.append((r, l))
        idx += 2
    meetings.sort()
    count = 0
    last_end = -1
    for r, l in meetings:
        if l >= last_end:
            count += 1
            last_end = r
    print(count)

main()

This editorial was generated by claude4.6opus-thinking.