Overview

This is a problem of selecting the maximum number of meetings from the given ones such that their time intervals do not overlap.

Analysis

This problem is known as the classic “Interval Scheduling Problem.” The goal is to select as many non-overlapping intervals as possible.

First, a naive approach would be to “try all combinations,” but since the number of meetings \(N\) can be up to \(2 \times 10^5\), an exhaustive search is not practical (the time complexity is exponential).

The key observation is that “the earlier the ending time of a selected meeting, the more room there is to fit additional meetings afterward.” In other words, a Greedy Algorithm is effective.

Specifically: - Sort all meetings in ascending order of their “ending time.” - After sorting, iterate through the meetings from the beginning and select a meeting if its start time is at or after the “ending time of the last selected meeting.”

The reason this greedy strategy yields an optimal solution is that by selecting meetings with earlier ending times, we maximize the flexibility to fit other meetings into the remaining time.

For example, consider the following input:

Sorting by end time gives the order A → C → B. We select A, then C can be selected, so the maximum number is 2.

On the other hand, if we select in order of earliest start time, we get A → B, and can only select 2, but this approach is incorrect in general.

Algorithm

1. Store all meetings in a list as \((L_i, R_i)\) pairs.
2. Sort the meetings in ascending order of “ending time \(R_i\).”
3. Select the first meeting and record its ending time.
4. Iterate through the remaining meetings in order, and select a meeting if its start time is “greater than or equal to the ending time of the last selected meeting.”
5. Output the number of selected meetings.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the meeting list)

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Intervals are handled as (L, R) pairs, and the sort key is specified as lambda x: x[1] (ending time).

• The ending time of the previously selected meeting is tracked with a variable last_end, and overlap is determined by comparing it with the start time of the current meeting.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    meetings = []
    index = 1
    for _ in range(N):
        L = int(data[index])
        R = int(data[index+1])
        meetings.append((L, R))
        index += 2
    
    # 終了時刻でソートする
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end = -1
    
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.