这是 LeetCode 3414. 不重叠区间的最大得分（Maximum Score of Non-overlapping Intervals），难度 Hard，是 Weekly Contest 431 的 Q4。

题目理解

- 每个区间 `intervals[i] = [li, ri, weighti]`
- 最多选 4 个互不重叠的区间（共享边界也算重叠）
- 得分 = 选中区间权重之和
- 返回得分最大且字典序最小的下标数组

解题思路

参考题解 ，核心思路：

1. 按左端点排序所有区间，同时保留原始下标
2. 记忆化搜索 DP：`dp(i, k)` 表示从排序后的第 `i` 个区间开始，还能选 `k` 个区间的最大得分方案
3. 对每个区间，有两种选择：
   - 跳过：`dp(i+1, k)`
   - 选它：需要找到第一个左端点 严格大于 当前区间右端点的位置 `j`，然后 `dp(j, k-1) + weighti`
4. 找 `j` 用二分查找优化到 O(log n)
5. 权重相同时，比较选中下标数组的字典序，保留字典序更小的

时间复杂度 O(n log n)，空间复杂度 O(n)。

Java 实现

```java
import java.util.*;

class Solution {
    // 状态记录：最大权重 和 选中的原始下标列表
    private static class State {
        long weight;
        List<Integer> selected;
        
        State(long weight, List<Integer> selected) {
            this.weight = weight;
            this.selected = selected;
        }
    }
    
    // 区间对象，按左端点排序
    private static class Interval {
        int left, right, weight, originalIndex;
        
        Interval(int left, int right, int weight, int originalIndex) {
            this.left = left;
            this.right = right;
            this.weight = weight;
            this.originalIndex = originalIndex;
        }
    }
    
    private List<Interval> intervals;
    private State[][] memo;
    
    public int[] maximumWeight(List<List<Integer>> intervalsInput) {
        int n = intervalsInput.size();
        
        // 转换为区间对象并保留原始下标
        intervals = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> interval = intervalsInput.get(i);
            intervals.add(new Interval(interval.get(0), interval.get(1), interval.get(2), i));
        }
        
        // 按左端点升序排序
        intervals.sort(Comparator.comparingInt(a -> a.left));
        
        // 记忆化数组：memo[i][k] 表示从第i个区间开始，还能选k个的最优状态
        memo = new State[n][5];
        
        State res = dp(0, 4);
        
        // 转换为int数组并排序（题目要求返回排序后的下标数组）
        int[] ans = new int[res.selected.size()];
        for (int i = 0; i < res.selected.size(); i++) {
            ans[i] = res.selected.get(i);
        }
        Arrays.sort(ans);
        return ans;
    }
    
    // 从第i个区间开始，还能选quota个区间的最大得分方案
    private State dp(int i, int quota) {
        if (i == intervals.size() || quota == 0) {
            return new State(0, new ArrayList<>());
        }
        if (memo[i][quota] != null) {
            return memo[i][quota];
        }
        
        // 选项1：跳过当前区间
        State skip = dp(i + 1, quota);
        
        // 选项2：选当前区间
        Interval cur = intervals.get(i);
        // 二分查找：第一个左端点严格大于cur.right的位置
        int j = findFirstGreater(i + 1, cur.right);
        State next = dp(j, quota - 1);
        
        List<Integer> newSelected = new ArrayList<>(next.selected);
        newSelected.add(cur.originalIndex);
        Collections.sort(newSelected);
        State pick = new State(cur.weight + next.weight, newSelected);
        
        // 比较：优先权重大的，权重相同选字典序小的
        State best;
        if (pick.weight > skip.weight) {
            best = pick;
        } else if (pick.weight < skip.weight) {
            best = skip;
        } else {
            // 权重相同，字典序比较
            best = compareLexicographically(pick.selected, skip.selected) < 0 ? pick : skip;
        }
        
        memo[i][quota] = best;
        return best;
    }
    
    // 二分查找：第一个左端点 > rightBoundary 的区间位置
    private int findFirstGreater(int startFrom, int rightBoundary) {
        int l = startFrom;
        int r = intervals.size();
        while (l < r) {
            int m = (l + r) >>> 1;
            if (intervals.get(m).left > rightBoundary) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
    
    // 字典序比较两个List<Integer>
    private int compareLexicographically(List<Integer> a, List<Integer> b) {
        int minSize = Math.min(a.size(), b.size());
        for (int i = 0; i < minSize; i++) {
            int cmp = Integer.compare(a.get(i), b.get(i));
            if (cmp != 0) return cmp;
        }
        return Integer.compare(a.size(), b.size());
    }
}
```

关键要点

要点    说明    
排序    按 `left` 升序，保证二分查找正确性    
不重叠判定    `next.left > cur.right`（严格大于，共享边界算重叠）    
二分查找    `findFirstGreater` 找第一个左端点 > 当前右端点的位置    
字典序处理    权重相同时，比较选中下标数组的字典序，选更小的    
返回排序    最终返回的数组需要按原始下标升序排列    

这个实现时间复杂度 O(n log n)，可以顺利通过 n = 5×10⁴ 的数据。