Overview

Given the start and end times of \(N\) meetings, determine whether there exists a moment when \(K\) or more meetings are being held simultaneously.

Analysis

The goal of this problem is to efficiently determine “how many meetings are being held simultaneously at any given point in time.”

Naive Approach (Why It Results in TLE)

For example, one could naively check how many meetings are taking place at each point in time. However, since the time range can be up to \(10^9\) and the number of meetings can be up to \(2 \times 10^5\), checking every possible time is impractical.

Additionally, examining each meeting’s start and end times one by one while computing overlapping interval combinations each time would be too slow.

Solution: Event Sorting (A Variation of the Imos Method)

The key insight is that only “the moments when meetings start” and “the moments when meetings end” matter. For each meeting, we consider the following two events: - At time \(S_i\): an event where “one meeting is added” - At time \(E_i\): an event where “one meeting is removed”

By “sorting these events by time” and processing them in order, we can efficiently simulate the number of concurrent meetings at any given moment.

Handling Cases Where Start and End Occur at the Same Time

For example, meeting A may end at time \(t\) while meeting B starts at time \(t\). In this case, by processing in the order “end → start,” we prevent unnecessary overcounting.

Specifically, processing in the following order ensures correctness: - At the same time, process end events (-1) first, then process start events (+1)

Algorithm

1. For each meeting, create a “+1” event for the start time \(S_i\) and a “-1” event for the end time \(E_i\).
2. Sort all events in “ascending order of time.” For events at the same time, ensure “-1 (end) is processed first.”
3. Process the sorted events from left to right, updating the current meeting count current_meetings.
4. Record the maximum number of concurrent meetings max_meetings, and output Yes if it is \(K\) or more.

Example

Input:

3 3
1 3
2 4
3 5

Event sequence (time, change):

(1, +1), (2, +1), (3, -1), (3, +1), (4, -1), (5, -1)

Since -1 is processed first at the same time, the actual order is:

(1, +1), (2, +1), (3, -1), (3, +1), (4, -1), (5, -1)

Processing steps: - Time 1: +1 → 1 meeting - Time 2: +1 → 2 meetings - Time 3: -1 → 1 meeting, then +1 → 2 meetings (maximum is 2) - Time 4: -1 → 1 meeting - Time 5: -1 → 0 meetings

The maximum number of concurrent meetings is 2, so for \(K=3\), the answer is No.

Complexity

• Time complexity: \(O(N \log N)\) → Dominated by sorting the events.
• Space complexity: \(O(N)\) → The event list has size \(2N\)

Implementation Notes

• Treat start times and end times as separate events (imos method-style thinking)

• Set the sort key as (time, delta) so that end events are processed before start events at the same time

• Use sys.stdin.read for fast input processing (important since \(N\) can be large)

  Source Code

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])

events = []

index = 2
for _ in range(N):
    s = int(data[index])
    e = int(data[index+1])
    index += 2
    events.append((s, 1))   # 開始イベント
    events.append((e, -1))  # 終了イベント

# イベントソート: 時刻で昇順、同じ時刻なら終了(-1)を先に処理
events.sort(key=lambda x: (x[0], x[1]))

current_meetings = 0
max_meetings = 0

for time, delta in events:
    current_meetings += delta
    max_meetings = max(max_meetings, current_meetings)

if max_meetings >= K:
    print("Yes")
else:
    print("No")

---

This editorial was generated by qwen3-coder-480b.