08.14 大疆笔试 后端开发工程师（研发部）B卷 AC

• end_i 表示小于等于end的最大end
• start_j 表示小于等于start的最大end

// 排序后
// start end weight
[2, 5,  3]
[1, 6, 2]
[3, 8, 10]
[7, 9, 5]
[7, 9, 10]
    
// [2, 5, 3] come, create [5, 3, [1]]
// list: [5, 3, [1]]
    
// [1, 6, 2] come, create [6, 2, [2]]
// choose: [6, 2, [2]] OR [5, 3, [1]]
// list: [5, 3, [1]], [6, 3, [1]]
    
// [3, 8, 10] come, create [8, 10, [3]]
// choose: [6, 3, [1]] OR [8, 10, [3]]
// list: [5, 3, [1]], [6, 3, [1]], [8, 10, [3]]
    
// [7, 9, 5] come, create [9, 5, [4]]
// choose: [6, 3, [1]] + [9, 5, [4]] OR [3, 8, [10]]
// list: [5, 3, [1]], [6, 3, [1]], [8, 10, [3]], [9, 10, [3]]
    
// [7, 9, 10] come, create [9, 10, [5]]
// choose: [6, 3, [1]] + [9, 10, [5]] OR [9, 10, [3]]
// list: [5, 3, [1]], [6, 3, [1]], [8, 10, [3]], [9, 13, [1, 5]]

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Solution {

    /* Write Code Here */
    public int[] schedule(int[][] arr) {
        int n = arr.length;
        // 记录数组对应的下标
        Map<int[], Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        // 根据结束时间排序
        Arrays.sort(arr, (a, b) -> a[2]-b[2]);
        // 结束时间
        ArrayList<EndStatus> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            EndStatus status = new EndStatus();
            if(list.isEmpty()) {
                status.endTime = arr[i][2];
                status.weight = arr[i][0];
                status.item = new ArrayList<>();
                status.item.add(i);
                list.add(status);
            } else if(list.get(0).endTime > arr[i][1]) { // 起始时间小于endTime // 寻找小于等于结束时间的最大的endTime，比较value值
                int nextIdx = findIdx(arr[i][2], list);
                s = list.get(nextIdx);
                if(s.endTime == status.endTime) {
                    if(s.weight < status.weight) {
                        list.set(nextIdx, status);
                    }
                }else if(s.weight < status.weight) {
                    list.add(status);
                }else{
                    status.weight = s.weight;
                    status.item = s.item;
                    list.add(status);
                }  
            } else { // 起始时间大于等于endTime
                // 寻找小于等于起始时间的最大的endTime，计算value值
                int preIdx = findIdx(arr[i][1], list);
                EndStatus s = list.get(preIdx);
                status.endTime = arr[i][2];
                status.weight = arr[i][0] + s.weight;
                List<Integer> tmp = new ArrayList<>(s.item);
                tmp.add(i);
                status.item = tmp;
                // 寻找小于等于结束时间的最大的endTime，比较value值
                int nextIdx = findIdx(arr[i][2], list);
                s = list.get(nextIdx);
                if(s.endTime == status.endTime) {
                    if(s.weight < status.weight) {
                        list.set(nextIdx, status);
                    }
                }else if(s.weight < status.weight) {
                    list.add(status);
                }else{
                    status.weight = s.weight;
                    status.item = s.item;
                    list.add(status);
                }
            }
        }
        int weightv = 0;
        List<Integer> retList = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            EndStatus s = list.get(i);
            if(s.weight > weightv) {
                weightv = s.weight;
                retList = s.item;
            }
        }
        int ret[] = new int[retList.size()];
        for(int i = 0; i < retList.size(); i++){
            ret[i] = map.get(arr[retList.get(i)]);
        }
        return ret;
    }

    private int findIdx(int time, ArrayList<EndStatus> list) {
        int left = 0, right = list.size()-1;
        while(left < right) {
            int mid = (left + right+1) / 2;
            int tmpTime = list.get(mid).endTime;
            if(tmpTime > time) {
                right = mid - 1;
            }else if (tmpTime == time){
                return mid;
            } else{
                left = mid;
            }
        }
        return left;
    }
}


class EndStatus{
    int endTime;//结束时间
    int weight;//权重
    List<Integer> item = new ArrayList<>();//任务下标
}