空气床onsite

感觉空气床DP其实考得不多

楼主能帮我看下这样做对吗？谢谢

1. class Solution {
   
2.     public static void main(String[] args) {
   
3.         Solution sol = new Solution();
   
4.         List<List<String>> input = new ArrayList<>();
   
5.         input.add(Arrays.asList("2-4", "100"));
   
6.         input.add(Arrays.asList("4-8", "200"));
   
7.         input.add(Arrays.asList("5-7", "300"));
   
8.         System.out.println(sol.findMaxProfit(input));
   
9.     }
   
10.    
    
11.     public int findMaxProfit(List<List<String>> input) {
    
12.         if (input == null || input.size() == 0) return 0;
    
13.         List<Interval> orders = new ArrayList<>();
    
14.         for (List<String> list : input) {
    
15.             String[] time = list.get(0).split("-");
    
16.             int start = Integer.parseInt(time[0]);
    
17.             int end = Integer.parseInt(time[1]);
    
18.             int profit = Integer.parseInt(list.get(1));
    
19.             orders.add(new Interval(start, end, profit));
    
20.         }
    
21.         Collections.sort(orders, (o1, o2) -> {
    
22.             return Integer.compare(o1.start, o2.start);
    
23.         });
    
24.         // DP => look back all results
    
25.         int[] M = new int[orders.size()];
    
26.         M[0] = orders.get(0).profit;
    
27.         int global = 0;
    
28.         for (int i = 1; i < orders.size(); i++) {
    
29.             int max = orders.get(i).profit;
    
30.             for (int j = 0; j < i; j++) {
    
31.                 if (orders.get(j).end <= orders.get(i).start) { // if no overlap
    
32.                     max = Math.max(max, M[j] + max);
    
33.                 }
    
34.             }
    
35.             M[i] = max;
    
36.             global = Math.max(global, max);
    
37.         }
    
38.         return global;
    
39.     }
    
40. }
    
41. 
    
42. class Interval {
    
43.     int start;
    
44.     int end;
    
45.     int profit;
    
46.     public Interval(int start, int end, int profit) {
    
47.         this.start = start;
    
48.         this.end = end;
    
49.         this.profit = profit;
    
50.     }
    
51. }
    
52.    

复制代码

补充内容 (2019-1-24 14:04):
32应该是max = Math.max(max, M[j] + orders.get(i).profit);

补充内容 (2019-1-24 14:06):
27 global = M[0]

请问楼主按照 start 还是 end time 来排序？

“7. coding:  新题，反正我没见过。题目是给你一堆24小时内旅店预定的信息，{{"2-4", "100"}, {"4-8", "200"}, {"5-7", "300"}}，要求找出收入最大的on-overlapping的时间段。现场写出来了。”

laecheng 发表于 2019-1-24 13:47
楼主能帮我看下这样做对吗？谢谢
[mw_shl_code=java,true]class Solution {
    public static void main ...

请问dp里面的M[n]代表什么？

感谢分享