Overview

Given the schedules of \(N\) meetings (start time \(S_i\), end time \(E_i\)), the problem asks to determine whether there exists a moment when \(K\) or more meetings are taking place simultaneously. Meetings are defined as half-open intervals \([S_i, E_i)\), meaning that at exactly time \(E_i\), the meeting is considered to have already ended.

Analysis

1. Limitations of Naive Approaches

First, since times can range over \(0 \leq S_i < E_i \leq 10^9\), it is impossible to count the number of meetings at each individual time point (e.g., every second). Additionally, comparing all pairs of meetings (approximately \(N^2\) pairs) to check for overlaps would be too slow (\(O(N^2)\)) given the constraint \(N = 2 \times 10^5\), and would not finish within the time limit.

2. Key Insight

The “number of simultaneously occurring meetings” changes only at the moment some meeting starts (\(S_i\)) or ends (\(E_i\)). At all other times, the number of meetings remains constant. Therefore, we can solve this efficiently by extracting only the start and end times of all meetings and examining them in chronological order.

3. Handling Half-Open Intervals

Since the problem states “from time \(S_i\) (inclusive) to time \(E_i\) (exclusive)”, if another meeting \(j\) starts at time \(E_i\) (i.e., \(E_i = S_j\)), they are not considered “simultaneous”. When processing events, if a “start” and an “end” occur at the same time, we can correctly count the number of simultaneous meetings by processing the “end” first.

Algorithm

Event Sorting (Sweep Line Method)

This problem can be solved efficiently using a technique called event sorting.

1. Create Events: For each meeting, create the following two events:
   • At time \(S_i\), the number of meetings increases by one (\(+1\))
   • At time \(E_i\), the number of meetings decreases by one (\(-1\))
2. Sort: Sort the \(2N\) created events in ascending order of time.
   • When times are equal, end events (\(-1\)) should be placed before start events (\(+1\)).
3. Sweep: Iterate through the sorted events from the beginning, updating the current meeting count current_count.
   • If current_count reaches \(K\) or more at any point, output Yes and terminate.
   • If current_count never reaches \(K\) or more after processing all events, output No.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Creating \(2N\) events takes \(O(N)\).
  • Sorting the events takes \(O(N \log N)\).
  • Sweeping through the events takes \(O(N)\).
  • Overall, sorting is the dominant factor.
• Space Complexity: \(O(N)\)
  • Required to store the \(2N\) events in a list.

Implementation Notes

• Fast Input: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() or similar methods can reduce execution time.

• Sorting Trick: When sorting tuples in Python, if the first elements are equal, comparison proceeds to the second element. By representing events as (time, delta) where end events have delta -1 and start events have delta 1, events at the same time will naturally have -1 (end) processed before 1 (start), correctly satisfying the problem’s half-open interval condition.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを効率的に処理できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 会議の件数 N と同時開催の上限 K を取得します。
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 各会議の開始時刻と終了時刻をイベントとしてリストに格納します。
    # 会議は [Si, Ei) の半開区間であるため、時刻 Ei では会議は終了しています。
    # スイープライン法（平面走査法）を用いて、同時に開催されている会議の数をカウントします。
    events = []
    for i in range(N):
        s = int(input_data[2 + 2*i])
        e = int(input_data[3 + 2*i])
        
        # 開始イベントを +1、終了イベントを -1 とします。
        # Pythonのタプルのソート順序を利用し、同じ時刻にイベントが重なった場合、
        # 終了イベント (-1) が開始イベント (1) よりも先に処理されるようにします。
        # これにより、時刻 Ei に別の会議が開始する場合でも、正しくカウントできます。
        events.append((s, 1))
        events.append((e, -1))
    
    # イベントを時刻順にソートします。時刻が同じ場合は、第2要素の -1 が 1 より先に来ます。
    events.sort()
    
    current_count = 0
    # 各イベントを順番に処理し、現在の会議数を更新していきます。
    for _, etype in events:
        current_count += etype
        
        # 同時に開催されている会議の数が K 以上になった瞬間があれば、Yes を出力して終了します。
        if current_count >= K:
            print("Yes")
            return
            
    # すべてのイベントを処理しても K 以上にならなければ、No を出力します。
    print("No")

if __name__ == '__main__':
    main()

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