Wedding Camera Timeline
A wedding photographer ran several cameras all day: her own, an assistant's, a drone, and a few cameras clipped to the tables. Each camera's photos are already in time order. Times are seconds relative to the start of the ceremony, so a shot taken 10 minutes before it is -600.
She wants one album timeline for the couple, with every photo from every camera in time order. Some cameras took thousands of shots, some took none, and two cameras can fire at the very same second.
Your task
Write mergeTimelines(cameras). cameras is a list of lists; each inner list holds one camera's photo times in non-decreasing order. Return a single list with every time from every camera, in non-decreasing order. Keep repeated times: each one is a separate photo.
An empty cameras list, or cameras with no photos, give an empty result. Aim for O(N log k) time for N photos and k cameras.
mergeTimelines(cameras: int[][]) → int[]
Examples
cameras = [[-600, 0, 45], [-30, 10], [5, 45, 90]]
[-600, -30, 0, 5, 10, 45, 45, 90]
At each step, look only at the earliest unused photo of each camera and take the smallest: -600, then -30, then 0, 5, 10. Both 45s are kept because they are two different photos.
cameras = [[], [12, 12], []]
[12, 12]
Two cameras took nothing. The result is just the other camera's photos.
cameras = []
[]
No cameras at all: an empty timeline.
Constraints
- 0 ≤ k = cameras.length ≤ 1,000
- 0 ≤ cameras[i].length ≤ 2,000, and N, the total number of photos, is at most 50,000
- -36,000 ≤ each time ≤ 86,400
- Each cameras[i] is sorted in non-decreasing order.
Start with brute force
Two obvious ways. One: pour every photo into one list and sort it. That is O(N log N) and correct, but it throws away the fact that each camera is already sorted, and it needs all photos in memory before producing the first one.
Two: merge the cameras one at a time into a growing album. The album gets merged again and again, so early photos are copied up to k times: O(N · k), which is 50 million steps for 50,000 photos on 1,000 cameras. Scanning all k camera fronts for each photo is O(N · k) too.
Hints
0 of 4 shown- Hint 1
With just two cameras, how would you merge their lists in one pass? Now picture three cameras. At any moment, which photos could possibly be the next one in the album?
- Hint 2
The next photo is always the earliest unused photo of some camera. So you only ever need to compare k candidates: one front photo per camera.
- Hint 3
Scanning all k fronts each time costs O(k) per photo. You need "give me the smallest candidate" and "replace it with the next photo from the same camera" to be fast. Which structure does both in O(log k)?
- Hint 4
Put each non-empty camera's first photo into a min-heap as
(time, camera, index). Repeatedly pop the smallest, append its time, and if that camera has another photo, push(next time, camera, index + 1). Stop when the heap is empty.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Merging two sorted lists means repeatedly taking the smaller of the two fronts. With k lists, the next item is the smallest of k fronts. A min-heap holds those k fronts, so finding the smallest and replacing it with that camera's next photo both cost O(log k).
Trace [[-600, 0, 45], [-30, 10], [5, 45, 90]]. Cameras are A, B, C.
- Heap starts with the fronts: A -600, B -30, C 5.
- Pop A -600. Push A's next, 0. Heap: B -30, A 0, C 5.
- Pop B -30. Push B 10. Heap: A 0, C 5, B 10.
- Pop A 0. Push A 45. Heap: C 5, B 10, A 45.
- Pop C 5, push C 45. Pop B 10; B is finished, push nothing. Heap: A 45, C 45.
- Pop A 45 (A is finished), pop C 45, push C 90, pop C 90. The heap is empty.
Album: -600, -30, 0, 5, 10, 45, 45, 90. The heap never held more than 3 entries, one per camera, however many photos there were. Storing the camera and index with each time is what lets you find "that camera's next photo" after a pop.
function mergeTimelines(cameras) {
const heap = []; // entries [time, camera, index], smallest time on top
const less = (a, b) => a[0] < b[0];
const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
const push = (entry) => {
heap.push(entry);
let i = heap.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (!less(heap[i], heap[parent])) break;
swap(i, parent);
i = parent;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length === 0) return top;
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && less(heap[l], heap[m])) m = l;
if (r < heap.length && less(heap[r], heap[m])) m = r;
if (m === i) break;
swap(i, m);
i = m;
}
return top;
};
cameras.forEach((cam, c) => { if (cam.length) push([cam[0], c, 0]); });
const album = [];
while (heap.length) {
const [time, c, i] = pop();
album.push(time);
if (i + 1 < cameras[c].length) push([cameras[c][i + 1], c, i + 1]);
}
return album;
}import heapq
def merge_timelines(cameras):
# one entry per camera: (time of its next photo, camera, index)
heap = [(cam[0], c, 0) for c, cam in enumerate(cameras) if cam]
heapq.heapify(heap)
album = []
while heap:
time, c, i = heapq.heappop(heap)
album.append(time)
if i + 1 < len(cameras[c]):
heapq.heappush(heap, (cameras[c][i + 1], c, i + 1))
return albumRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.