Hall Booking: Most Events

A seminar hall receives booking requests, each with a start and end time. Two events can use the hall one after the other if the first ends at or before the time the second starts. Which maximum number of events can the hall host?

Examples

Example 1

Input:  events = [[1, 3], [2, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]
Output: 4

Taking [1, 3], [3, 5], [5, 7] and [8, 9] fills the day without any overlap, because each event starts exactly when (or after) the previous one ends. The long [0, 6] booking would block three of them by itself, so the best count is 4.

Example 2

Input:  events = [[1, 2], [1, 2]]
Output: 1

Constraints

events holds one row per request, [start, end], in no particular order.

An event that ends exactly when another starts is fine — the hall is free at that moment. Return how many events can be hosted, not which ones.

How to solve it

Hint

“Maximum number of non-overlapping intervals” — the classic activity selection. Always keep the event that finishes earliest: it leaves the most room for the rest.

Approach: Interval scheduling: sort by end time

Sort events by end time.
Keep last_end. If an event starts ≥ last_end, take it and update last_end.

Check with the example. Pick (1,3), (3,5), (5,7), (8,9) → 4 events.

Complexity: O(n log n) time.

The reference solutions in all four languages are in the Solutions tab of the workspace below.