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里没有无符号长整形ulong，需要借助Long.compareUnsigned(x,y)来比较）

代码```
class Solution {
public int[] maximumWeight(List<List<Integer>> intervals) {
int n = intervals.size();
// 需要一个额外的元素存储原序号，同时也加速了intervals的访问速度
int[][] sorted = new int[n][4];
for (int i = 0; i < n; i++) {
List<Integer> list = intervals.get(i);
sorted[i][0] = list.get(0);
sorted[i][1] = list.get(1);
sorted[i][2] = list.get(2);
sorted[i][3] = i;
}
// 按照结束时间排序
Arrays.sort(sorted, (a, b) -> a[1] - b[1]);
// 顺序记录可能的终点与权重，可根据二分查找找到能选当前区间的最大权重
List<long[]> dp = new ArrayList<>();
// 顺序记录权重对应的最小字典序元素序号
List<long[]> records = new ArrayList<>();
// 添加dp边界便于计算
dp.add(new long[]{-1, 0, 0, 0, 0});
records.add(new long[]{-1, 0, 0, 0, 0});
for (int i = 0; i < n; i++) {
int[] interval = sorted[i];
// 二分找到最后一个不重叠的区间
int l = 0, r = dp.size();
while (l < r) {
int m = (l + r) >> 1;
if (dp.get(m)[0] < interval[0]) {
l = m + 1;
} else {
r = m;
}
}
// 不重叠的区间最大权重和序号位置
long[] touch = dp.get(l - 1);
long[] touchRecord = records.get(l - 1);
// 上一个区间的最大权重和序号位置
long[] last = dp.getLast();
long[] lastRecord = records.getLast();
// 到当前区间结束最大权重和序号位置
long[] cur = Arrays.copyOf(last, last.length);
long[] curRecord = Arrays.copyOf(lastRecord, lastRecord.length);
int w = interval[2];
// 当前区间原序号，其实最后版本已经不用+1了，但是没改。
long x = interval[3] + 1;
cur[0] = interval[1];
// 更新4个元素的权重和序号位置
if (w > last[1]) {
cur[1] = w;
curRecord[1] = buildRecord(0, x, 1);
} else if (w == last[1]) {
long tmpRecord = buildRecord(0, x, 1);
curRecord[1] = Long.compareUnsigned(tmpRecord, lastRecord[1]) < 0 ? tmpRecord : lastRecord[1];
}
if (touch[1] > 0) {
if (touch[1] + w > last[2]) {
cur[2] = touch[1] + w;
curRecord[2] = buildRecord(touchRecord[1], x, 2);
} else if (touch[1] + w == last[2]) {
long tmpRecord = buildRecord(touchRecord[1], x, 2);
curRecord[2] = Long.compareUnsigned(tmpRecord, lastRecord[2]) < 0 ? tmpRecord : lastRecord[2];
}
}
if (touch[2] > 0) {
if (touch[2] + w > last[3]) {
cur[3] = touch[2] + w;
curRecord[3] = buildRecord(touchRecord[2], x, 3);
} else if (touch[2] + w == last[3]) {
long tmpRecord = buildRecord(touchRecord[2], x, 3);
curRecord[3] = Long.compareUnsigned(tmpRecord, lastRecord[3]) < 0 ? tmpRecord : lastRecord[3];
}
}
if (touch[3] > 0) {
if (touch[3] + w > last[4]) {
cur[4] = touch[3] + w;
curRecord[4] = buildRecord(touchRecord[3], x, 4);
} else if (touch[3] + w == last[4]) {
long tmpRecord = buildRecord(touchRecord[3], x, 4);
curRecord[4] = Long.compareUnsigned(tmpRecord, lastRecord[4]) < 0 ? tmpRecord : lastRecord[4];
}
}
dp.add(cur);
records.add(curRecord);
}
long[] record = records.getLast();
long max = 0;
long[] last = dp.getLast();
int[] ans = new int[4];
// 求出选1、2、3、4分别的最大权重和序号位置
for (int i = 1; i <= 4; i++) {
if (last[i] < max) {
continue;
}
int[] tmp = new int[4];
long r = record[i];
tmp[0] = (int) (r >> 48 & 0xffff) - 1;
tmp[1] = (int) (r >> 32 & 0xffff) - 1;
tmp[2] = (int) (r >> 16 & 0xffff) - 1;
tmp[3] = (int) (r & 0xffff) - 1;
tmp = Arrays.copyOf(tmp, i);
if (last[i] > max || Arrays.compare(tmp, ans) < 0) {
ans = tmp;
max = last[i];
}
}
return ans;
}

// 构造新的序号位置，通过冒泡更新记录使字典序最小
private long buildRecord(long lastRecord, long x, int idx) {
for (--idx; idx > 0; idx--) {
long y = lastRecord >> (4 - idx) * 16 & 0xffff;
if (x < y) {
lastRecord = lastRecord ^ (y << (4 - idx) 16) | (y << (4 - idx - 1) 16);
} else {
break;
}
}
return lastRecord | (x << (4 - idx - 1) * 16);
}
}