室内设计网站界面,做微商截图的网站,做的好的音乐网站,广州市网站建设 骏域动力题目描述#xff1a;给定一个区间数组#xff0c;[[1,2,3],[3,4,2],[2,4,4]]#xff0c;每个区间有价值#xff0c;求在获取k个区间的条件下面#xff0c;求获得的最大的价值#xff0c;关键是dp的定义和二分查找的写法#xff08;小于tar额最右下标#xff09; import… 题目描述给定一个区间数组[[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 Comparatorint[]() {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;}
}
