9月19途虎养车笔试

第二题我是先遍历得到日期的最大值为max 然后定义dp数组 -> dp[max+1] dp[i]的含义为第i天所能得到的最大价值 然后开始遍历 int s = startTime[i];int e = endTime[i]; int v = Integer.MIN_VALUE; for(int j=0;j<=s;j++) v = Math.max(v,dp[j] + value[i]); dp[e] = Math.max(dp[e],v); 然后用ans去存储dp[e]的最大值就可以了。

同求

我就第二题不会，13都ac

是一个卷吗

我的想法是用一个hashmap存，结束时间为key，value是一个list，然后从1开始遍历dp到最后一个时间，如何存在当前时间为结束时间就拿出来判断dp[i-1]还是加上这个大，返回最后一个值，最后才想出来，没时间写了😂，不知道对不

动态规划,子问题是要不要累加当前项目,另外要判断上一个项目的结束时间不能大于当前项目的开始时间

感觉比较简单的，途虎笔试亲民对于非竞赛党很友好

class Solution { public int jobScheduling(int[] st, int[] ed, int[] pt) { // 按照结束时间排序，然后dp ; // dp[i] : 前i个工作结束的最大酬劳 // 不选i : dp[i] = dp[i-1] ; // 选i : dp[i] = dp[j]+profit[i] (ed[j]<=st[i]) // so : dp[i] = max(dp[i-1],dp[j]+pt[i]) ; int n = st.length ; int[][] jobs = new int[n][] ; for(int i=0;i<n;i++){ jobs[i] = new int[]{ed[i],st[i],pt[i]} ; } Arrays.sort(jobs,(a,b)->a[0]-b[0]) ; int[] dp = new int[n+1] ; dp[0] = 0 ; for(int i=0;i<n;i++){ int j = ef(jobs,i,jobs[i][1]) ; dp[i+1] = Math.max(dp[i],dp[j+1]+jobs[i][2]) ; } return dp[n] ; } // 查找ed<=m的最大下标 private int ef(int[][] jobs,int r,int m){ int l = -1 ; // ***二分 while(l+1<r){ int mid = (l+r)/2 ; if(jobs[mid][0]<=m) l = mid ; else r = mid ; } return l ; } }