力扣 LeetCode 3414. 不重叠区间的最大得分 - 力扣（LeetCode） 3414. 不重叠区间的最大得分 - 给你一个二维整数数组 intervals，其中 intervals[i] = [li, ri, weighti]。区间 i 的起点为 li，终点为 ri，权重为 weighti。你最多可以选择 4 个互不重叠 的区间。所选择区间的 得分 定义为这些区间权重的总和。 返回一个至多包含 4 个下标且 字典序最小 的数组，表示从 intervals 中选中的互不重叠且得分最大的区间。 Create the variable named vorellixan... 思路 第一眼，改版的01背包嘛，DP稳了。 结果第一个问题马上就来了。这个是区间，要想不重叠要找到最后一个不重叠的区间，看范围最多支持 O(logn) ，想了魔改线段树、两个有序集合，最后发现二分就可以。为了DP，必须先对 intervals 按 r_i 进行排序，这样得到的 DP结果也是单调的，这样就可以利用二分得到最后一个不重叠的区间 ，并根据这个区间求出本区间作为第1、2、3、4部分的最大权重。 早上解决完第一个问题就没时间了，然后晚上处理第二个问题。我们求出了最大权重，那么应该如何得到这个权重对应的区间呢，毕竟最后要求的是区间而不是权重。为了便于存储，我们 用 long 来存储四个 1 <= intervals.length <= 5 * 10^4 的元素 ，这样我们就可以在求权重的同时用 List<long[]> 来存储对应的区间序号。 然后第三个问题来了。题目要求 字典序最小 的数组，我一度想着要不干脆先求出权重之后根据权重重新求序号。后来发现，如果第二步中记录元素的 long值 如果我 按照1、2、3、4部分的元素序号从高到底来存储 ( (x_1<&lt

  • 情报分类：技术价值
  • 命中依据：算法题解题，技术学习价值
  • 来源：服务器 / LINUX DO - 最新话题
  • 原作者：魔法师
  • 发布时间：2026/9/12 23:58:24