Overview

Treat each meeting as two events: “+1 at start, -1 at end.” Process events in chronological order, counting the number of overlapping meetings, and determine whether the number of simultaneous meetings ever reaches \(K\) or more.

Analysis

Meeting \(i\) takes place during the interval \([S_i, E_i)\) (inclusive of start, exclusive of end). Therefore, “how many meetings are happening at a given time” can be managed as a quantity that increases at starts and decreases at ends as time progresses.

Even if we tried to naively check each time point, times can be up to \(10^9\), making it impossible to scan all time points. Also, checking overlaps for all pairs of meetings would be \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

Instead, we focus only on the start and end times of meetings. Since the overlap count changes only at start or end times, it suffices to sort these events and process them in order.

A point that requires special attention is when an end and a start occur at the same time. Since intervals are \([S, E)\), for example, if at time \(t\) “one meeting ends and another meeting starts,” then at time \(t\) the ended meeting is no longer counted, while the started meeting is counted. In other words, at the same time, we need to process ends (-1) before starts (+1).

Algorithm

1. For each meeting \((S_i, E_i)\), create the following 2 events:
   • Start event: \((S_i, +1)\)
   • End event: \((E_i, -1)\)
2. Sort all events in ascending order of time. If times are the same, order them so that end (-1) comes before start (+1).
3. Starting with cur (current number of simultaneous meetings) at 0, process events in order:
   • Apply the change d with cur += d
   • If cur >= K, such a moment exists, so output Yes and terminate
4. If we reach the end without triggering the condition, output No

(Concrete example) When meetings are \([1,3)\) and \([3,5)\), at time 3 the former has ended and the latter has started, so the overlap count is 1. The events are \((1,+1),(3,-1),(3,+1),(5,-1)\), and by processing -1 first at time 3, we correctly count the overlap.

Complexity

• Time complexity: \(O(N \log N)\) (sorting \(2N\) events)
• Space complexity: \(O(N)\) (event array)

Implementation Notes

• Use (time, change) as the sort key, ensuring -1 comes before +1 (in Python, -1 < +1 holds naturally, so no special handling is needed).

• Since the input can be large, using sys.stdin.buffer.read() allows for faster reading.

• Terminating immediately when cur >= K is reached avoids unnecessary processing.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    K = int(next(it))

    events = []
    for _ in range(N):
        s = int(next(it)); e = int(next(it))
        events.append((s, 1))   # start
        events.append((e, -1))  # end

    events.sort(key=lambda x: (x[0], x[1]))  # end(-1) before start(+1) at same time

    cur = 0
    for _, d in events:
        cur += d
        if cur >= K:
            sys.stdout.write("Yes\n")
            return
    sys.stdout.write("No\n")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.