Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Intervals

Fewest meeting rooms for a day of meetings

Medium · Target 18 minutes · Intervals · Type asked atBloombergGoogleAmazon

Each meeting is a pair [start, end] with start < end, running from start up to end. A meeting that ends at time t frees its room for one that starts at t. Return the smallest number of rooms that lets every meeting take place.

Examples

InputOutputWhy
meetings = [[0, 30], [5, 10], [15, 20]]2The long meeting needs a room all day; the other two can share a second.
meetings = [[1, 5], [5, 10]]1The second starts exactly when the first ends.
meetings = [[1, 10], [2, 9], [3, 8], [4, 7]]4All four are running at time 4.

Constraints

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ start < end ≤ 10⁹

Hints

Hint 1

Forget which meeting goes in which room. What single number about the day decides how many rooms you need?

Hint 2

It is the largest number of meetings running at the same moment. That number only changes when a meeting starts or ends.

Hint 3

Sort the start times and the end times separately. Walk through the starts; before each one, release every room whose meeting has ended by then.

Where people lose marks

  • Using < instead of ≤ when comparing an end with a start, which counts back-to-back meetings as overlapping.
  • Counting overlapping pairs: three meetings that pairwise overlap at different times may still need only two rooms.
  • Sorting the meetings once by start and comparing only neighbours: a long early meeting can overlap many later ones.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.