Maximum Earnings From Taxi LeetCode solution in JavaScript

1
// Same as https://leetcode.com/problems/maximum-profit-in-job-scheduling/
2
// Time -> O(nlogn), where n = length of rides array
3
// Space -> O(n), where n = length of rides array
4

5
/**
6
 * @param {number} n
7
 * @param {number[][]} rides
8
 * @return {number}
9
 */
10
var maxTaxiEarnings = function (n, rides) {
11
  const len = rides.length;
12

13
  rides.sort((a, b) => {
14
    return a[1] - b[1];
15
  });
16

17
  // Binary search
18
  function binarySearch(idx) {
19
    let low = 0,
20
      high = idx;
21

22
    while (low < high) {
23
      let mid = Math.trunc((low + high) / 2);
24

25
      if (rides[mid][1] <= rides[idx][0]) low = mid + 1;
26
      else high = mid;
27
    }
28

29
    return high === 0 ? -1 : high - 1;
30
  }
31

32
  let dp = new Array(len).fill(0);
33
  dp[0] = rides[0][2] + (rides[0][1] - rides[0][0]);
34

35
  for (let i = 1; i < len; i++) {
36
    dp[i] = rides[i][2] + (rides[i][1] - rides[i][0]);
37
    let j = binarySearch(i);
38

39
    if (j !== -1) dp[i] += dp[j];
40

41
    dp[i] = Math.max(dp[i], dp[i - 1]);
42
  }
43

44
  return dp[len - 1];
45
};