Maximum Profit in Job Scheduling LeetCode solution in JavaScript

1
var jobScheduling = function (startTime, endTime, profit) {
2
  const N = startTime.length;
3

4
  let zip = [];
5
  for (let i = 0; i < N; i++) {
6
    zip.push([startTime[i], endTime[i], profit[i]]);
7
  }
8
  const starts = mergesort(zip, (a, b) => a[0] - b[0]).map((s) => s[0]);
9
  const endAsc = mergesort(zip, (a, b) => a[1] - b[1]);
10
  const ends = endAsc.map((s) => s[1]);
11

12
  const startToClosestEnd = {};
13
  let j = 0;
14
  for (const start of starts) {
15
    let curEnd = ends[j];
16
    let nextEnd = ends[j + 1];
17
    // While the current and next end are before the current start...
18
    while (curEnd <= start && nextEnd && nextEnd <= start) {
19
      // Advance one end.
20
      j++;
21
      curEnd = ends[j];
22
      nextEnd = ends[j + 1];
23
    }
24

25
    if (curEnd <= start) {
26
      startToClosestEnd[start] = curEnd;
27
    } else {
28
      startToClosestEnd[start] = null;
29
    }
30
  }
31

32
  let maxProfit = Number.MIN_SAFE_INTEGER;
33

34
  const bestAtEnd = {};
35
  for (const [start, end, profit] of endAsc) {
36
    if (startToClosestEnd[start]) {
37
      maxProfit = Math.max(
38
        maxProfit,
39
        bestAtEnd[startToClosestEnd[start]] + profit
40
      );
41
    } else {
42
      maxProfit = Math.max(maxProfit, profit);
43
    }
44

45
    bestAtEnd[end] = maxProfit;
46
  }
47

48
  return maxProfit;
49
};
50

51
function mergesort(arr, comparator) {
52
  if (arr.length === 1) return arr;
53

54
  const mid = Math.floor((arr.length - 1) / 2);
55
  const a = mergesort(arr.slice(0, mid + 1), comparator);
56
  const b = mergesort(arr.slice(mid + 1), comparator);
57
  const c = [];
58

59
  while (a.length || b.length) {
60
    if (a.length && b.length) {
61
      if (comparator(a[0], b[0]) < 0) {
62
        c.push(a.shift());
63
      } else {
64
        c.push(b.shift());
65
      }
66
    } else if (b.length) {
67
      c.push(b.shift());
68
    } else {
69
      c.push(a.shift());
70
    }
71
  }
72

73
  return c;
74
}