Leetcode每日一题 —— 3414. 不重叠区间的最大得分

作者：#魔法师 板块：#开发调优 力扣 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<<48)|(x_2<<32)|(x_3<<16)|x_4 )，那么比较它们就可以 O(1) 的时间比较出字典序最小的区间。（其实发现有个坑，java里