Daily Coding Day Twenty One

, ,

One, two, skip a few…twenty one! This one was marked as Easy in the email, and out of the ones I have solved recently was the most fun because it made me think about heaps which, while foundational, I don’t find myself really every using. My daily choice is often driven by my opinon on data structures in general.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//Good morning! Here's your coding interview problem for today.
//This problem was asked by Snapchat.
//Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.
//For example, given [(30, 75), (0, 50), (60, 150)], you should return 2.

function meetingRooms(intervals) {
    if (intervals.length === 0) {
        return 0;
    }

    // sort intervals by duration
    intervals.sort((a, b) => a[0] - b[0]);

    // init a *cough*heap
    const endTimes = [];

    // heap push function
    function pushHeap(heap, item) {
        heap.push(item);
        let i = heap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (heap[parent] <= heap[i]) break;
            [heap[parent], heap[i]] = [heap[i], heap[parent]];
            i = parent;
        }
    }

    // heap pop function
    function popHeap(heap) {
        if (heap.length === 1) return heap.pop();
        const top = heap[0];
        heap[0] = heap.pop();
        let i = 0;
        while (true) {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let smallest = i;
            if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
            if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
            if (smallest === i) break;
            [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
            i = smallest;
        }
        return top;
    }

    // add first meeting
    pushHeap(endTimes, intervals[0][1]);

    for (let i = 1; i < intervals.length; i++) {
        // reuse the earliest room if it is free
        if (intervals[i][0] >= endTimes[0]) {
            popHeap(endTimes);
        }

        // add the current meeting's end time
        pushHeap(endTimes, intervals[i][1]);
    }

    // heap size is the # of rooms required
    // not to be confused with the room of requirement
    return endTimes.length;
}