Snap新鲜出炉电面挂经...哭...求大米安慰

tipoup2011 发表于 2019-5-17 12:58
先根据end sort，[s1,e1], [s2,e2]...[si,ei]...，然后dp代表截止到第i天的结果，dp只有当i属于e的时候再更 ...

我的基本思路一样 但是因该不用天 而是用number of interval 当作 dp dimention,

是不是 六四六的解法

1. public static void main(String[] args) {
   
2.         Playground pg = new Playground();
   
3.         int[][] intervals1 = new int[][]{{1,3}, {4,10}, {4,6}, {9,10}};
   
4.         int[][] intervals2 = new int[][]{{1,3}, {8,9}, {2,100}, {99, 300}};
   
5.         System.out.println(pg.getMaxProfit(intervals1));        System.out.println(pg.getMaxProfit(intervals2));
   
6.     }
   
7.   
   
8.     public int getMaxProfit(int[][] intervals){
   
9.         Arrays.sort(intervals, (a,b) -> (a[1] - b[1]));
   
10.         int n = intervals.length;
    
11.         int[] dp = new int[n];
    
12.         int max = 0;
    
13.         for(int i = 0; i < n; i++) {
    
14.             dp[i] = intervals[i][1] - intervals[i][0]; // initial value is the current interval
    
15.             for(int j = 0; j < i; j++) {
    
16.                 if(intervals[i][0] >= intervals[j][1]) {
    
17.                     dp[i] = Math.max(dp[i], dp[j] + intervals[i][1] - intervals[i][0]); // dp[i] represents the maximum profit on if ith interval is included
    
18.                     max = Math.max(max, dp[i]);
    
19.                 }
    
20.             }
    
21.         }
    
22.         return max * 100;
    
23.     }
    

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

思路
对于任意一个interval，以它结尾的合理schedule的所有可能性是：它自己加上比他早结束的任意0个，1个或多个 intervals。
因为所有interval的时间跨度都是正数，所以可以贪心地认为以某个interval结束的schedule所包含的intervals最多的那个就代表了以它结束的最大收益。
为了方便地找比当前结束更早的interval，我们可以按interval 结束的时间从小到大排序（开始时间怎么排都无所谓）。

code

1. class Solution {
   
2.     public int maxProfitAirBnb(int[][] reservations) {
   
3.         Arrays.sort(reservations, ((o1, o2) -> o1[1] - o2[1]));
   
4.         
   
5.         int res = 0;
   
6.         int[] memo = new int[reservations.length];
   
7. 
   
8.         for (int i = 0; i < reservations.length; i++) {
   
9.             int max = 0;
   
10.             for (int j = 0; j < i; j++) {
    
11.                 if (reservations[j][1] <= reservations[i][0]) {
    
12.                     max = Math.max(max, memo[j]);
    
13.                 }
    
14.             }
    
15.             memo[i] = max + (reservations[i][1] - reservations[i][0]);
    
16.             res = Math.max(res, memo[i]);
    
17.         }
    
18. 
    
19.         return res * 100;
    
20.     }
    
21. }

复制代码

好像新题，请教楼主面的他家哪个office?