Interval Scheduling And Calendar Systems

What's being tested

Interval scheduling problems test whether you can model time ranges precisely, sort/merge bookings, and search for overlaps or gaps efficiently. Uber-style variants often add calendar-system constraints: cancellations, multiple participants, meeting rooms, time zones, and scalable aggregation with MapReduce/Spark.

Patterns & templates

• Half-open intervals [start, end) simplify overlap checks: two intervals conflict when a.start < b.end && b.start < a.end.

• Sort-and-scan merge runs in O(n log n) time; sort by start, merge adjacent/overlapping intervals, then inspect gaps.

• Two-pointer availability search finds earliest common slot across two sorted calendars in O(n + m); advance the interval ending earlier.

• Min-heap room allocation uses heapq by earliest end time; O(n log k) for assigning or finding an available room.

• Binary search over sorted bookings checks one room’s availability in O(log n) plus neighbor overlap checks via bisect_left.

• Sweep line events convert intervals to (time, +1/-1) deltas; sort events to compute concurrent meetings, free capacity, or aggregate load.

• Distributed aggregation maps intervals to time buckets or event deltas, reduces by key, and handles skew with salting or hierarchical combining.

Common pitfalls

• Pitfall: Treating intervals as closed [start, end] causes false conflicts when one meeting ends exactly as another starts.

• Pitfall: Ignoring cancellations or updates leads to stale availability; model bookings with status/version, not just append-only intervals.

• Pitfall: Mixing local times across users breaks correctness; normalize to UTC internally and only localize at input/output boundaries.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.