Maximum Earnings From Taxi LeetCode solution in Java

1
class Solution {
2
  private static class Job {
3
    private int start;
4
    private int end;
5
    private int profit;
6

7
    public Job(int start, int end, int profit) {
8
      this.start = start;
9
      this.end = end;
10
      this.profit = profit;
11
    }
12
  }
13

14
  private int binarySearch(Job jobs[], int index) {
15
    int low = 0;
16
    int high = index - 1;
17
    int ans = -1;
18
    while (low <= high) {
19
      int mid = low + (high - low) / 2;
20
      if (jobs[mid].end <= jobs[index].start) {
21
        ans = mid;
22
        low = mid + 1;
23
      } else {
24
        high = mid - 1;
25
      }
26
    }
27
    return ans;
28
  }
29

30
  public long maxTaxiEarnings(int n, int[][] rides) {
31
    Job jobs[] = new Job[rides.length];
32
    for (int i = 0; i < rides.length; i++) {
33
      jobs[i] = new Job(rides[i][0], rides[i][1], rides[i][1] - rides[i][0] + rides[i][2]);
34
    }
35
    Arrays.sort(jobs, (j1, j2) -> (j1.end - j2.end));
36
    long[] dp = new long[rides.length];
37
    dp[0] = jobs[0].profit;
38
    for (int i = 1; i < jobs.length; i++) {
39
      long include = jobs[i].profit;
40
      int index = binarySearch(jobs, i);
41
      if (index != -1) {
42
        include += dp[index];
43
      }
44
      dp[i] = Math.max(include, dp[i - 1]);
45
    }
46
    return dp[rides.length - 1];
47
  }
48
}