动态规划+二分查找

题目描述：给定一个区间数组，[[1,2,3],[3,4,2],[2,4,4]]，每个区间有价值，求在获取k个区间的条件下面，求获得的最大的价值，关键是dp的定义和二分查找的写法（小于tar额最右下标）

import java.util.*;import java.util.*;
import java.util.*;//[[1,2,3],[3,4,2],[2,4,4]],2class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 计算小明面试成功可能性的最大和* @param interviews int整型二维数组 interviews[i] = [startTime_i, endTime_i, possibility_i] 第 i 个面试在 startTime_i 时间开始， endTime_i 时间结束，通过的可能性是 possibility_i* @param k int整型 最多参加的面试次数* @return int整型*/
//    int [][]nums = new int[][] {{1,2,3},{3,4,2},{2,4,6}};public static void main(String[] args) {int [][]nums = new int[][] {{1,2,3},{3,4,2},{2,4,6},{3,4,9},{4,5,10}};System.out.println(maxValue(nums, 2));}public static int maxValue (int[][] interviews, int k) {// write code hereint n = interviews.length;Arrays.sort(interviews, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}});int dp [][] =new int[n + 1][k + 1];for (int i = 0 ; i <= n; i++){dp[i] = new int[k + 1];}// dp[i][j] 表示前i个面试，参加了k场的总和for (int i = 1 ; i <= n ; i++){int start = interviews[i - 1][0];int index = search(0 , i -1 , start , interviews); // 前面最近的位置for (int j = 1; j <= k && j <= i; j++){dp[i][j] = Integer.max(dp[i-1][j] , dp[i][j]);if (index +1 == i) { // 本身dp[i][j] = Integer.max( interviews[i-1][2] , dp[i][j]);}else {dp[i][j] = Integer.max(dp[index + 1][j-1] + interviews[i-1][2] , dp[i][j]); // 非本身}}}return dp[n][k];}// 找出小于tar的最右下标public static int search(int left , int right , int tar , int[][] interviews){int res = right;while(left <= right){int mid = left + (right - left) / 2;int cur = interviews[mid][1];if (cur >= tar){right = mid - 1;}else {left = mid + 1;}}if (right < 0){return res;}return right;}
}