Overview

This is a problem where, given a single meeting room, we need to find the maximum number of meetings that can be scheduled without any time overlaps. This is known as the “Interval Scheduling Problem,” one of the classic problems solved using a greedy algorithm.

Analysis

To solve this problem, we consider what criteria to use when selecting meetings.

• Select in order of earliest start time \(L_i\): This is inappropriate because if there is even one meeting that starts very early and ends very late (e.g., 0:00–23:00), it could prevent many other shorter meetings from being scheduled.
• Select in order of shortest duration (\(R_i - L_i\)): This is inappropriate because even a short meeting, if positioned exactly in the middle between two other meetings, could eliminate both of those meetings by being selected.

The optimal strategy is to “select in order of earliest end time \(R_i\)”. The earlier a meeting ends, the more remaining time becomes available afterward, increasing the possibility of fitting in more meetings. This approach of “always choosing the locally best option (the one that ends earliest)” is called a greedy algorithm.

Algorithm

1. Store each meeting’s information as a list of pairs (end time \(R_i\), start time \(L_i\)).
2. Sort the list in ascending order of end time \(R_i\).
3. Initialize a variable current_end_time to \(0\), representing “the time at which the meeting room becomes available.”
4. Examine each meeting in sorted order and perform the following:
   • If the meeting’s start time \(L_i\) is greater than or equal to current_end_time, adopt that meeting.
   • If adopted, increment the total meeting count by \(+1\) and update current_end_time to that meeting’s end time \(R_i\).
5. Output the final total count.

Complexity

• Time complexity: \(O(N \log N)\)
  • Reading the meeting information takes \(O(N)\), sorting by end time takes \(O(N \log N)\), and the subsequent scan takes \(O(N)\). The overall bottleneck is the sorting step.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the information of \(N\) meetings in a list.

Implementation Notes

• Sorting trick: Python’s sort() method, when sorting a list of tuples, compares by “first element, then second element, …” in order. Therefore, by creating tuples in the order (end time, start time), you can simply sort them without specifying any arguments to achieve the desired order.

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), using sys.stdin.read().split() or similar methods to read all input at once can reduce execution time.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 会議の数 N
    n = int(input_data[0])
    
    # 各会議を (終了時刻, 開始時刻) のタプルとしてリストに格納
    # 終了時刻でソートするため、終了時刻を第一要素にする
    meetings = []
    for i in range(n):
        l = int(input_data[2 * i + 1])
        r = int(input_data[2 * i + 2])
        meetings.append((r, l))
    
    # 終了時刻が早い順にソート（区間スケジューリング問題の最適解）
    meetings.sort()
    
    count = 0
    current_end_time = 0
    
    for r, l in meetings:
        # 現在の会議の開始時刻が、直前に選んだ会議の終了時刻以降であれば採用
        if l >= current_end_time:
            count += 1
            current_end_time = r
            
    # 最大の会議数を出力
    print(count)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.