We need to build a calendar system that accepts or rejects event bookings. Each event occupies a half-open interval [start, end), meaning the event includes the start time but excludes the end time. This is the standard convention for time intervals because it lets adjacent events sit back-to-back without conflict. An event ending at 20 and another starting at 20 do not overlap.

The core challenge is detecting overlaps. Two intervals [s1, e1) and [s2, e2) overlap if and only if s1 < e2 AND s2 < e1. If either condition fails, the intervals are disjoint. This overlap condition is the foundation for every approach we'll discuss.

So the problem reduces to: maintain a collection of non-overlapping intervals. For each new interval, check if it conflicts with any existing one. If not, add it. If it does, reject it.

Key Constraints:

Intuition

Keep a list of all booked events. When a new booking comes in, check it against every existing event for overlaps. If none overlap, add the new event to the list.

Two intervals [s1, e1) and [s2, e2) overlap when s1 < e2 AND s2 < e1. To see why, start from the opposite case. The intervals are disjoint only if one ends at or before the other starts: either e1 <= s2 (first ends before second starts) or e2 <= s1 (second ends before first starts). Negating that disjoint condition gives s1 < e2 AND s2 < e1, the overlap condition.

Algorithm

Example Walkthrough

Code

For each new booking, we scan through every existing event, including the many that sit far from the new interval and cannot overlap it. Keeping the events sorted lets us jump directly to the two that could overlap.

Intuition

If we keep our bookings sorted by start time, a new interval [start, end) can only overlap with its immediate neighbors in the sorted order. We find where the new interval would be inserted in the sorted list and check the intervals just before and just after that position.

Only the two neighbors can conflict because the stored intervals are themselves non-overlapping and sorted by start. The predecessor has the largest start that is still at or below start; any interval further left ends even earlier, so if the predecessor does not reach start, none of them do. The successor has the smallest start above start; any interval further right starts even later, so if end does not reach the successor's start, it reaches none of them. Checking the two neighbors therefore rules out every possible overlap.

Algorithm

Example Walkthrough

Code

The binary search finds neighbors in O(log n), but the array insertion still costs O(n) because shifting elements is unavoidable in a contiguous array. A balanced tree supports both search and insertion in O(log n).

Intuition

A balanced binary search tree (Java's TreeMap, C++'s map, Python's SortedList) gives us both O(log n) search and O(log n) insertion. It keeps the sorted-order neighbor-checking logic from Approach 2 but replaces the array, so insertion no longer needs O(n) shifts.

In a TreeMap, floorEntry finds the closest event starting at or before the new start, and ceilingEntry finds the closest event starting at or after the new start. Check both neighbors for overlap, and if there is no conflict, insert the new event.

The correctness argument is the same as Approach 2. All stored intervals are non-overlapping and sorted, so only the immediate neighbors can conflict with a new interval. The change here is purely in the data structure: a balanced tree performs the floor and ceiling lookups and the insertion all in O(log n) because it never shifts elements.

Not every language ships a balanced map with floor and ceiling lookups. Go, JavaScript, TypeScript, and C# below keep a sorted array and binary search for the neighbors instead. The lookups are O(log n) but insertion stays O(n) because of array shifting, matching Approach 2's cost in those languages.

Algorithm

Example Walkthrough

Code