Overview

This is a problem where we select some meetings such that their time intervals do not overlap, maximizing the number of meetings that can be held. The optimal solution is obtained by greedily selecting meetings in order of earliest ending time.

Analysis

This problem is a classic “interval scheduling (activity selection problem).”

• Treating meeting \(i\) as an interval \((L_i, R_i)\), the non-overlapping condition means:
  When selecting meetings in some order, “the start time \(L\) of the next selected meeting must be greater than or equal to the end time \(R\) of the previously selected meeting (\(L \ge R\)).”
  ※ Since \(R_i = L_j\) counts as non-overlapping, the condition is \(L \ge \text{last\_end}\).

• If we naively try to “find the maximum count by exhaustive search,” there are \(2^N\) combinations of selecting/not selecting each meeting, which is far too slow.
  Also, even considering DP, since times can be up to \(10^9\), a “time-axis DP” is infeasible, and with \(N=2\times 10^5\), an \(O(N^2)\) DP (e.g., linearly searching for previously selectable meetings each time) would also TLE.

• The key insight is that the earlier a meeting ends, the easier it is to fit more meetings afterward.
  For example, if two meetings have similar start times, choosing the one that ends earlier increases the number of candidate meetings that can be selected next.

Using this intuition rigorously, the greedy approach of “sorting by ending time in ascending order and selecting meetings that fit in order” is optimal.

Algorithm

1. Sort all meetings in ascending order by ending time \(R\).
2. Maintain a variable last_end representing “the ending time of the last selected meeting” (initialized to a sufficiently small value).
3. Iterate through the meetings \((L, R)\) in sorted order. If \(L \ge \text{last\_end}\), the meeting does not overlap, so select it:
   • Increment the selection count by \(+1\)
   • Update last_end = R
4. The final selection count is the answer.

Why This Is Optimal (Intuitive Explanation)

Selecting the meeting with the earliest ending time leaves the most remaining time afterward.
If you select a different meeting with a later ending time, you reduce the possibility of selecting subsequent meetings by that much, making it harder to achieve the maximum count.

Complexity

• Time complexity: Dominated by sorting, so \(O(N \log N)\)
• Space complexity: \(O(N)\) for storing the array of intervals

Implementation Notes

• The non-overlapping check is \(L \ge \text{last\_end}\) (including equality). If you use \(L > \text{last\_end}\) instead, consecutive meetings where \(R_i = L_j\) will be incorrectly rejected, causing WA.

• In the code, intervals are stored as (R, L) for easy sorting (since Python tuples are compared starting from the first element).

• The initial value of last_end just needs to be sufficiently smaller than the lower bound of the input; in the code, it is set to -10**19.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    intervals = []
    for _ in range(N):
        L, R = map(int, input().split())
        intervals.append((R, L))
    intervals.sort()

    cnt = 0
    last_end = -10**19
    for R, L in intervals:
        if L >= last_end:
            cnt += 1
            last_end = R

    print(cnt)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.