Maximum Number of Events That Can Be Attended LeetCode solution in JavaScript

1
/**
2
 * O(nlogn)
3
 */
4
var maxEvents = function (events) {
5
  // sort events by their start time
6
  events.sort((a, b) => a[0] - b[0]);
7

8
  // create priority queue to sort events by end time, the events that have saem start time
9
  let minHeap = new PriorityQueue((a, b) => a - b);
10
  let i = 0,
11
    len = events.length,
12
    res = 0,
13
    d = 0;
14

15
  while (i < len || !minHeap.isEmpty()) {
16
    if (minHeap.isEmpty()) d = events[i][0]; // start with event from events list
17

18
    while (i < len && events[i][0] <= d)
19
      // Add all events that have start time <= day `d` into PQ
20
      minHeap.add(events[i++][1]); // add ending time to the minHeap, so when we pull we get event that is ending first
21

22
    minHeap.poll(); // make sure we have some event attent
23
    ++res;
24
    ++d;
25

26
    // we finished task of day 'd' Remove events that are already closed ie endTime < d as we cant attend it
27
    while (!minHeap.isEmpty() && minHeap.peek() < d) minHeap.poll();
28
  }
29
  return res;
30
};
31

32
/*******************standard priority queue implementation used in all leetcode javascript solutions****************/
33
class PriorityQueue {
34
  /**
35
   * Create a Heap
36
   * @param {function} compareFunction - compares child and parent element
37
   * to see if they should swap. If return value is less than 0 it will
38
   * swap to prioritize the child.
39
   */
40
  constructor(compareFunction) {
41
    this.store = [];
42
    this.compareFunction = compareFunction;
43
  }
44

45
  peek() {
46
    return this.store[0];
47
  }
48

49
  size() {
50
    return this.store.length;
51
  }
52
  isEmpty() {
53
    return this.store.length === 0;
54
  }
55

56
  poll() {
57
    if (this.size() < 2) {
58
      return this.store.pop();
59
    }
60
    const result = this.store[0];
61
    this.store[0] = this.store.pop();
62
    this.heapifyDown(0);
63
    return result;
64
  }
65

66
  add(val) {
67
    this.store.push(val);
68
    this.heapifyUp(this.size() - 1);
69
  }
70

71
  heapifyUp(child) {
72
    while (child) {
73
      const parent = Math.floor((child - 1) / 2);
74

75
      if (this.shouldSwap(child, parent)) {
76
        [this.store[child], this.store[parent]] = [
77
          this.store[parent],
78
          this.store[child],
79
        ];
80
        child = parent;
81
      } else {
82
        return child;
83
      }
84
    }
85
  }
86

87
  heapifyDown(parent) {
88
    while (true) {
89
      let [child, child2] = [1, 2]
90
        .map((x) => parent * 2 + x)
91
        .filter((x) => x < this.size());
92
      if (this.shouldSwap(child2, child)) {
93
        child = child2;
94
      }
95

96
      if (this.shouldSwap(child, parent)) {
97
        [this.store[child], this.store[parent]] = [
98
          this.store[parent],
99
          this.store[child],
100
        ];
101
        parent = child;
102
      } else {
103
        return parent;
104
      }
105
    }
106
  }
107

108
  shouldSwap(child, parent) {
109
    return (
110
      child && this.compareFunction(this.store[child], this.store[parent]) < 0
111
    );
112
  }
113
}