Find conflicting calendar events booked in the same room

Given a list of calendar events, each with an id, a room, a start and an end, find the events that conflict: two events conflict when they are in the same room and their times overlap. Return every conflicting pair. Do better than comparing every pair of events.

Interface

Unless you agree on a different interface with the interviewer, assume:

• find_conflicts(events: list[tuple[str, str, int, int]]) -> list[tuple[str, str]] — each event is (id, room, start, end) with times as half-open [start, end). Return pairs (a, b) with a < b, sorted.

Example

events = [
  ("e1", "A", 9, 11), ("e2", "A", 10, 12), ("e3", "A", 11, 13),
  ("e4", "B", 9, 10), ("e5", "B", 9, 17), ("e6", "A", 14, 15),
]
find_conflicts(events)  ->  [("e1", "e2"), ("e2", "e3"), ("e4", "e5")]
# e1 and e3 only touch at 11; e6 is alone

Constraints

• Up to 10^5 events; times are integers.

Clarifying questions

• Do touching events (one ends when the next starts) conflict?
• Is "conflict" per room, per attendee, or global?
• Return pairs, or just the ids of events that have any conflict?
• How many conflicts can there be? The output itself can be quadratic.

What a strong answer covers

• Group by room, sort each group by start, then sweep with a set (or heap) of events still running: each new event conflicts with every running event.
• O(n log n + c) time, where c is the number of conflicting pairs.
• Removing finished events before comparing, so touching events don't count.
• Tests: no conflicts, one long event over many short ones, identical times.

Follow-ups

• Return only the ids that have at least one conflict, in O(n log n).
• The fewest events to cancel so nothing conflicts.
• Events are added and removed live: report new conflicts as they happen.