Overview

Given the time slots of \(N\) meetings, this problem asks us to determine whether there exists a moment when \(K\) or more meetings overlap simultaneously. It can be solved efficiently using the “imos method” (event sorting).

Analysis

Naive Approach and Its Issues

The simplest method is to count “how many meetings are taking place at each moment” for all time points. However, since the time range spans from \(0\) to \(10^9\), checking all time points would be \(O(10^9)\), which is far too slow.

Key Insight

The number of simultaneous meetings changes only at the moment a meeting starts and the moment a meeting ends. For \(N\) meetings, there are at most \(2N\) events where changes occur. In other words, we don’t need to check all time points — it suffices to check only the time points where events occur.

Concrete Example

For example, if there are 3 meetings \([1, 5)\), \([2, 8)\), \([3, 6)\), arranging the events chronologically:

If \(K = 3\), then at time 3 the simultaneous count reaches 3, so we output Yes.

Algorithm

1. Create events: For each meeting \(i\), create an event of \(+1\) (one more meeting) at start time \(S_i\) and an event of \(-1\) (one fewer meeting) at end time \(E_i\).
2. Sort events: Sort all events in ascending order of time. When times are equal, the default sort causes \(-1\) (end) to be processed before \(+1\) (start). This is consistent with the interpretation that end time \(E_i\) means “used until strictly less than \(E_i\)”, so at exactly time \(E_i\) that meeting has already ended.
3. Scan: Process events in order while updating the current simultaneous count current. If current reaches \(K\) or more at any point, output Yes and terminate.
4. If \(K\) or more is never reached after processing all events, output No.

Complexity

• Time complexity: \(O(N \log N)\) (sorting events is the bottleneck)
• Space complexity: \(O(N)\) (storing the event list)

Implementation Notes

• Sort order of events: When sorting by tuple \((time, change)\), events with change \(-1\) (end) come before \(+1\) (start) at the same time. This is consistent with the problem’s half-open interval definition where meetings last from time \(S_i\) inclusive to \(E_i\) exclusive. In other words, if one meeting ends at time \(t\) and another meeting starts at time \(t\), they are not considered “simultaneous”.

• Fast input: Using sys.stdin.buffer.read() allows reading large amounts of input quickly. Since \(N\) can be up to \(2 \times 10^5\), this is more efficient than repeatedly calling input().

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    events = []
    for i in range(N):
        S = int(input_data[idx]); idx += 1
        E = int(input_data[idx]); idx += 1
        events.append((S, 1))
        events.append((E, -1))
    
    events.sort()
    
    current = 0
    for time, delta in events:
        current += delta
        if current >= K:
            print("Yes")
            return
    
    print("No")

main()

This editorial was generated by claude4.6opus-thinking.