Preview Cue Ledger
Kth entry across arithmetic sequences ordered by value and source index
A music streaming service records preview cues emitted by several listening rooms.
Each row of rooms is [start, interval, count]. That room emits exactly count cues, at timestamps
start, start + interval, ..., start + (count - 1) * interval.
Room indices are their zero-based positions in rooms. The service combines all cues into one ledger, ordered by timestamp. When multiple rooms emit a cue at the same timestamp, those cues appear in increasing room-index order. Every cue is a separate ledger entry, even when timestamps match.
Given the one-based ledger position k, return [timestamp, room_index] for the cue at that position.
You must determine the requested entry without constructing the entire ledger.
Examples
Example 1
Input: rooms = [[2,4,3],[1,3,4]], k = 5 Output: [7,1]
Room 0 emits at timestamps 2, 6, and 10. Room 1 emits at 1, 4, 7, and 10. The fifth ledger entry is room 1's cue at timestamp 7.
Example 2
Input: rooms = [[5,2,3],[5,3,2],[5,10,1]], k = 2 Output: [5,1]
The first three entries all have timestamp 5, ordered by room indices 0, 1, and 2. The second entry therefore belongs to room 1.
Example 3
Input: rooms = [[0,7,4]], k = 4 Output: [21,0]
There is only one room, so its fourth cue is also the fourth ledger entry. Its timestamp is 0 + 3 * 7.
Constraints
- 1 <= rooms.length <= 1500
- Each row of rooms contains exactly three integers: [start, interval, count].
- 0 <= start <= 10^9
- 1 <= interval <= 10^6
- 1 <= count <= 10^6
- 1 <= k <= the sum of all room counts
The reference solutions use O(n log T) time and O(1) auxiliary space, where n is the number of rooms and T is one more than the largest cue timestamp. All timestamp arithmetic is within JavaScript's exact integer range.
Hints
Show hint 1Hint 1
For a proposed timestamp, compute how many cues each room has emitted by then using arithmetic rather than iteration.
Show hint 2Hint 2
Find the earliest timestamp whose cumulative cue count reaches k. Then account for cues strictly before that timestamp and scan the rooms in index order to resolve ties.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the one-based cue number within its room as well?
- How would the counting function change if each room could have several nonoverlapping runs of regularly spaced cues?
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