[leetcode 1235] [动态规划]

简单题

1. 线段树可做
   2.动态规划可做

import java.util.Arrays;
import java.util.Comparator;class Solution {int n;int[][] lcs;public static void main(String[] args) {Solution solution = new Solution();int ans = solution.jobScheduling(new int[]{1,2,3,3}, new int[]{3,4,5,6}, new int[]{50,10,40,70});System.out.println(ans);}public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {n = startTime.length;int[][] arr = new int[n][3];for (int i = 0; i < n; i++) {arr[i] = new int[]{startTime[i], endTime[i], profit[i]};}Arrays.sort(arr, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}});//lcs = new int[n][2];lcs[0][0] = 0;lcs[0][1] = arr[0][2];//for (int i = 1; i < n; i++) {lcs[i][0] = Math.max(lcs[i - 1][0], lcs[i-1][1]);int b = arr[i][0];int p = upperBound(arr, 0, i, b);if (p == 0) {// 不存在比b更小的数lcs[i][1] = arr[i][2];}else {// 存在比b更小的数lcs[i][1] = Math.max(lcs[p-1][0], lcs[p-1][1]) + arr[i][2];}}return Math.max(lcs[n-1][0], lcs[n-1][1]);}/*** 第一个大于target的数，*      如果没有找到， 那么返回to这个位置*      如果找到了，那么返回在数组中的位置** @param arr* @param from* @param to* @param target* @return*/public int upperBound(int[][] arr, int from, int to, int target) {int l = from;int r = to;while( l < r) {int mid = (l + r) /2 ;if ( arr[mid][1] <= target) {l =  mid + 1;}else {r = mid ;}}return l;}
}