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

class Solution {
    static class Job implements Comparable<Job> {
        int l, r, w;
        int idx;
        Job(int l, int r, int w, int idx) {
            this.l = l;
            this.r = r;
            this.w = w;
            this.idx = idx;
        }
        @Override
        public int compareTo(Job obj) {
            return Integer.compare(r, obj.r);
        }
    }
    public int jobScheduling(int[] sts, int[] eds, int[] w) {
            int n = sts.length;
            Job[] arr = new Job[n];
            for (int i=0; i<n; ++i) {
                arr[i] = new Job(sts[i], eds[i], w[i], i);
            }
            Arrays.sort(arr);

            int[] dp = new int[n+1];
            int[] states = new int[n+1];
            for (int i=1; i<=n; ++i) {
                dp[i] = dp[i-1];

                int l = -1, r = i-2;
                while (l < r) {
                    int mi = l + (r - l + 1) / 2;
                    if (arr[mi].r <= arr[i-1].l) l = mi;
                    else r = mi - 1;
                }
                // dp[i] = Math.max(dp[i], dp[l + 1] + arr[i-1].w);
                int t = dp[l + 1] + arr[i-1].w;
                if (t > dp[i]) {
                    // 选
                    dp[i] = t;
                    states[i] = l + 1;
                } else {
                    // 不选，用负数标记
                    states[i] = i - 1 - n;
                }
            }
            // 路径
            ArrayDeque<Integer> ret = new ArrayDeque<>();
            int i = n;
            while (i != 0) {
                int t = states[i];
                if (t < 0) {
                    // 不选
                    t += n;
                } else {
                    // 选
                    ret.offerFirst(arr[i-1].idx);
                }
                i = t;
            }

            System.out.println(ret);

            return dp[n];
    }
}