Overview

This is a problem of finding the maximum number of meetings that can be selected from meeting room reservation requests such that no two meetings overlap in time.

Analysis

This problem is a classic problem known as the interval scheduling problem. A naive approach would be to try all combinations, but since \(N\) can be up to 200,000, an \(O(2^N)\) brute-force search is not practical.

The key observation is that a greedy algorithm of “selecting meetings in order of earliest ending time” yields the optimal solution. This is because choosing meetings with earlier ending times increases the possibility of fitting more meetings afterward.

Algorithm

1. Sort all meetings in ascending order by their ending time \(R_i\)
2. Initialize the current ending time to -1 (so that the first meeting can always be selected)
3. Process the sorted meetings in order:
   • If the current meeting’s start time \(L_i\) is greater than or equal to the current ending time
   • Select this meeting and increment the count
   • Update the current ending time to this meeting’s ending time \(R_i\)
4. Output the number of selected meetings

For example, if the meetings are [(1,3), (2,4), (3,5)], sorting by ending time gives the same order. First, we select (1,3). Next, (2,4) is not selected because its start time 2 is less than the current ending time 3. Then, (3,5) is selected because its start time 3 is greater than or equal to the current ending time 3. As a result, we can select 2 meetings.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by the sorting step)
• Space complexity: \(O(N)\) (array to store the meeting data)

Implementation Notes

• To sort efficiently, placing the ending time as the first element of a tuple makes sorting by ending time straightforward

• Setting the initial value of the current ending time to -1 ensures that the first meeting is always selected

• Since we read input as integers, we use split() to parse the data

  Source Code

import sys

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

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.