League Replay Channel Roster

Assign smallest available IDs to intervals in start-time and index order

MediumIntervalsHeapSorting

A football league streams match replays through numbered broadcast channels. Each replay needs one channel for its entire reserved time window.

You are given windows, where windows[i] = [start, end] reserves the half-open interval [start, end) for replay i. A channel becomes available exactly at end, so another replay may start on that channel at the same time.

Assign channels using this precise policy:

  1. Process replays in increasing order of start time. When start times are equal, process the replay with the smaller original index first.
  2. Assign each replay the smallest positive channel number that is currently available. Channel numbers have no upper limit.

Return an integer array channels in the original input order, where channels[i] is the channel assigned to replay i.

This policy uses the minimum possible number of channels while also determining one unique assignment. Return an empty array when there are no replays.

Examples

Example 1

Input: windows = [[2,4],[0,3],[4,6]]
Output: [2,1,1]

The replay at index 1 starts first and takes channel 1. Index 0 starts while that channel is occupied, so it takes channel 2. At time 4, both channels have become available, and index 2 takes the smaller one.

Example 2

Input: windows = [[5,9],[5,7],[5,8]]
Output: [1,2,3]

All three replays start together, so their original indices determine processing order. Each needs a different channel because none has finished when the others start.

Example 3

Input: windows = [[0,2],[2,4],[4,6]]
Output: [1,1,1]

Each replay starts exactly when the preceding replay finishes. Half-open windows allow all of them to reuse channel 1.

Constraints

  • 0 <= windows.length <= 3000
  • Each element of windows contains exactly two integers: start and end.
  • 0 <= start < end <= 1000000
  • The windows may be unsorted, overlapping, or identical.

The intended solution runs in O(n log n) time and uses O(n) auxiliary space. Channel numbering starts at 1, and output positions always correspond to original replay indices.

Hints

Show hint 1

Sort replay indices by start time and then by original index. Before assigning a replay, release every channel whose reservation has ended.

Show hint 2

Maintain one min-heap ordered by reservation end time and another min-heap containing available channel numbers.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you return only the minimum number of channels, without constructing the assignment?
  • If each channel needs a fixed cooldown after a replay finishes, how would the availability rule change?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem