这是 LeetCode 3414. 不重叠区间的最大得分Maximum Score of Non-overlapping Intervals难度 Hard是 Weekly Contest 431 的 Q4。题目理解- 每个区间 intervals[i] [li, ri, weighti]- 最多选 4 个互不重叠的区间共享边界也算重叠- 得分 选中区间权重之和- 返回得分最大且字典序最小的下标数组解题思路参考题解 核心思路1. 按左端点排序所有区间同时保留原始下标2. 记忆化搜索 DPdp(i, k) 表示从排序后的第 i 个区间开始还能选 k 个区间的最大得分方案3. 对每个区间有两种选择- 跳过dp(i1, k)- 选它需要找到第一个左端点 严格大于 当前区间右端点的位置 j然后 dp(j, k-1) weighti4. 找 j 用二分查找优化到 O(log n)5. 权重相同时比较选中下标数组的字典序保留字典序更小的时间复杂度 O(n log n)空间复杂度 O(n)。Java 实现javaimport java.util.*;class Solution {// 状态记录最大权重 和 选中的原始下标列表private static class State {long weight;ListInteger selected;State(long weight, ListInteger 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 ListInterval intervals;private State[][] memo;public int[] maximumWeight(ListListInteger intervalsInput) {int n intervalsInput.size();// 转换为区间对象并保留原始下标intervals new ArrayList();for (int i 0; i n; i) {ListInteger 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);ListInteger 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;}// 字典序比较两个ListIntegerprivate int compareLexicographically(ListInteger a, ListInteger 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⁴ 的数据。