Overview

Given the start and end times of meetings, the problem asks to determine whether there is any moment when \(K\) or more meetings are being held simultaneously.

Analysis

For each meeting interval \([S_i, E_i)\), we need to find how many meetings are occurring simultaneously at each point in time. A naive approach of checking every possible time is impractical since the maximum value of \(E_i\) can be as large as \(10^9\). Instead, by focusing only on the start and end times of meetings and processing these event points (starts and ends) in chronological order, we can efficiently compute the overlap count.

Algorithm

We use an event-based sweep line method. For each meeting, we create a “+1” event at the start time and a “-1” event at the end time. We sort these events in ascending order of time, and when times are equal, we process end events (-1) before start events (+1) (this ensures that meetings ending at a given time are processed before meetings starting at that time, allowing us to correctly count overlaps). We process the sorted events in order while computing the current overlap count, and as soon as it reaches \(K\) or more, we output “Yes”. If we finish processing all events without ever reaching \(K\) or more, we output “No”.

Complexity

• Time complexity: \(O(N \log N)\)
  • The number of events is \(2N\), and sorting takes \(O(N \log N)\). The sweep processing takes \(O(N)\).
• Space complexity: \(O(N)\)
  • The array to store events has size \(2N\).

Implementation Notes

• Events are represented as tuples of (time, type), where type is +1 for start and -1 for end.

• When sorting, end events (-1) should be processed before start events (+1) at the same time. This ensures that meetings ending at a given time are handled before new meetings starting at that time, allowing the overlap count to be computed correctly.

• While updating the variable that holds the current overlap count, output “Yes” immediately and terminate as soon as it reaches \(K\) or more.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    n = int(data[0])
    k = int(data[1])
    events = []
    index = 2
    
    for i in range(n):
        s = int(data[index])
        e = int(data[index + 1])
        index += 2
        events.append((s, 1))
        events.append((e, -1))
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    current = 0
    for time, typ in events:
        current += typ
        if current >= k:
            print("Yes")
            return
            
    print("No")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.