Busiest Studio
HardIntervals
Problem
A recording facility has studios studios numbered 0 to studios - 1. Each booking in sessions is [start, end], a half-open range [start, end); all start times are distinct.
Sessions are assigned in order of their start time. A session goes to the lowest-numbered studio that is free at its start. If none is free, the session waits until the earliest moment a studio frees up (if several free up at that moment, it takes the lowest-numbered one) and then runs for its original duration. A delayed session keeps its place in the order: sessions with earlier original starts are always placed first.
Return the number of the studio that hosts the most sessions. If there is a tie, return the lowest number.
Example 1
- Input:
- studios = 2, sessions = [[0, 10], [1, 5], [2, 7], [3, 4]]
- Output:
- 0
0 → studio 0 until 10; 1 → studio 1 until 5; [2, 7) waits for studio 1 and runs [5, 10); [3, 4) waits until 10, when both free up, takes studio 0 and runs [10, 11). Both studios host 2 sessions, so the answer is 0.
Example 2
- Input:
- studios = 3, sessions = [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]
- Output:
- 1
Studios 0, 1, 2 take the first three. [4, 9) waits for studio 2 and runs [5, 10). [6, 8) waits until 10, when studios 1 and 2 both free up; it takes studio 1. Studios 1 and 2 host 2 each → 1.
Constraints
- 1 ≤ studios ≤ 100
- 1 ≤ sessions.length ≤ 10^5
- 0 ≤ start < end ≤ 5·10^5
- All start times are distinct.
Hint
Show the first hint
At each session start you need two things fast: the lowest-numbered free studio, and the studio that frees up earliest.
Walkthrough
How to approach it
01Clarify before coding
- Does a delayed session keep its full duration? Yes, it runs end - start units from whenever it actually begins.
- Ties when several studios free up at the same moment? The lowest-numbered one wins.
- Are the sessions given sorted? No; sort by start first.
02Brute force
For each session, scan all studios for the lowest free one, or for the earliest-freeing one if none is free.
Cost: O(n · s) time with s studios: 10^7 here, which passes, but it does not scale if the number of studios grows to n.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.