Free Intervals lessonsIntervals · Stage 1 · Sweep line · Step 2

The busiest moment

Find the earliest time at which the most meetings are running, by turning each meeting into a plus event at its start and a minus event at its end. About 20 minutes.

Two events per meeting

To find the busiest moment you do not need whole meetings, only the instants where the count of running meetings changes. Each meeting adds one at its start and takes one away at its end.

Make a list of events, a time and a change of +1 or −1. Sorted by time, walking the list while adding the changes gives the count of running meetings after each event.

Start: adds one to the count.

End: takes one away.

Ties and the peak

At the same time, handle ends before starts: a meeting ending at 10 does not overlap one starting at 10. Sorting pairs of time and change does this, since −1 sorts before +1.

Track the largest count seen. Only update it when the count is strictly bigger, so the answer is the first time the peak is reached. Return −1 if there are no meetings.

Sort pairs: by time, then −1 before +1.

Update the peak: only when strictly bigger.

In code

best = cur = 0
cur += change
best = max(best, cur)

Meetings [2, 4], [3, 7], [6, 9]. Events: +1 at 2, +1 at 3, −1 at 4, +1 at 6, −1 at 7, −1 at 9.

At time 2 the count is 1. A new peak: busiest time so far is 2.

Move 1 of 5

Quick check

Meetings [1, 3] and [3, 5]. What is the highest count at any moment?

Show the answer

1. At time 3 the first ends before the second starts, so only one is running.

Your problem

Busiest moment

You are given meetings, each as [start, end), occupying from start up to but not including end. Return the earliest time at which the greatest number of meetings are running. If there are no meetings, return −1.

Example

meetings = [[1, 5], [2, 6], [4, 8]] → 4

0 ≤ meetings.length ≤ 100,000 · 0 ≤ start < end ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.