难度困难
题目描述
给你一个二维整数数组 meetings，其中 meetings[i] = [starti, endi, revenuei] 表示一场会议从时间 starti 开始，在时间 endi 结束，并可获得 revenuei 的收益。
所有会议均采用 左闭右开区间 [start, end) 表示，因此仅在端点处相接的会议 不视为 重叠。
你可以选择任意一个会议 非空子集 ，所选会议两两不重叠。每选择一场会议，你都可以获得该会议对应的收益。
将所选会议按照 开始时间递增 的顺序排列。对于该顺序中每一对相邻会议，你还可以根据它们之间的空闲时间获得额外收益，每单位空闲时间获得 1 单位收益。空闲时间等于后一场会议的开始时间减去前一场会议的结束时间。
最早一场所选会议开始之前，以及最晚一场所选会议结束之后的空闲时间不会产生收益。如果只选择一场会议，则不会获得任何空闲时间收益。
返回可以获得的 最大总收益 。
数组的 子集 是从数组中选择若干元素得到的集合。
示例 1：
输入： meetings = [[2,5,4],[6,8,3]]
输出： 8
解释：
- 选择两场会议。它们互不重叠，会议收益为
4 + 3 = 7。 - 第一场会议在时间 5 结束，第二场会议在时间 6 开始，因此中间的空闲时间可额外获得
6 - 5 = 1 单位收益。 - 最大总收益为
7 + 1 = 8。
示例 2：
输入： meetings = [[3,5,4],[4,7,8],[8,10,3]]
输出： 12
解释：
- 选择下标为 1 和 2 的会议。它们互不重叠，会议收益为
8 + 3 = 11。 - 按时间顺序，这两场会议分别从时间 4 到 7、从时间 8 到 10。中间的空闲时间可额外获得
8 - 7 = 1 单位收益。 - 最大总收益为
11 + 1 = 12。
示例 3：
输入： meetings = [[1,2,2],[4,5,2],[7,9,3]]
输出： 11
解释：
- 选择全部三场会议。它们互不重叠，会议收益为
2 + 2 + 3 = 7。 - 从时间 2 到 4 的空闲时间可额外获得
4 - 2 = 2 单位收益。 - 从时间 5 到 7 的空闲时间可额外获得
7 - 5 = 2 单位收益。 - 最大总收益为
7 + 2 + 2 = 11。
提示
1 <= meetings.length <= 105meetings[i] = [starti, endi, revenuei]0 <= starti < endi <= 1091 <= revenuei <= 109
解法
方法一：排序 + 二分 + 动态规划
思考
会议数量可以到 \(10^5\)，枚举子集不行。收益来自两部分：选中会议本身的收入，以及按开始时间排好后、相邻两场之间的空档。只选一场时没有空档。
把某场会议固定成方案里的最后一场。能排在它前面的会议，结束时间不能晚于它的开始时间，新增空档是 \(\textit{start}\) 减去前一场的结束时间。需要最大化的量就是“以某场会议结尾的收益，再减去这场会议的结束时间”。
按结束时间排序之后，能接在当前会议前面的会议构成一个前缀，前缀最大值可以用二分定位。收益和空档都用 \(64\) 位整数累加。
将会议按结束时间升序排序。记 \(f[i]\) 为最后一场选第 \(i\) 场会议时能得到的最大收益。任意非空方案都有一场结束最晚的会议，所以答案是所有 \(f[i]\) 的最大值。
只选第 \(i\) 场时， \(f[i]=\textit{revenue}_i\)。若在它前面再接一场满足 \(\textit{end}_j\le\textit{start}_i\) 的会议 \(j\)，则
\[ f[i]=f[j]+\textit{revenue}_i+(\textit{start}_i-\textit{end}_j), \]
也就是
\[ f[i]=\textit{revenue}_i+\textit{start}_i+\max_j(f[j]-\textit{end}_j). \]
排序之后，这些 \(j\) 是一个前缀。令
\[ \textit{preMax}[k]=\max_{j<k}(f[j]-\textit{end}_j), \]
还没有任何会议时写成足够小的哨兵。处理第 \(i\) 场时，在下标 \([0,i)\) 中二分第一个结束时间大于 \(\textit{start}_i\) 的位置 \(p\)，则 \(\textit{preMax}[p]\) 就是上式里的最大值。若 \(\textit{start}_i\) 比全局最早的结束时间还小，这个前缀是空的，只能单选第 \(i\) 场。
然后令 \(\textit{preMax}[i+1]=\max(\textit{preMax}[i], f[i]-\textit{end}_i)\)。结束时间相同的两场会议一定重叠，二分不会把它们接在一起。
时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def maxEarnings(self, meetings: list[list[int]]) -> int:
n = len(meetings)
meetings.sort(key=lambda x: x[1])
pre_max = [-inf] * (n + 1)
ans = 0
for i, (start, end, revenue) in enumerate(meetings):
val = revenue
if start >= meetings[0][1]:
j = bisect_right(meetings, start, hi=i, key=lambda x: x[1])
val += pre_max[j] + start
ans = max(ans, val)
pre_max[i + 1] = max(pre_max[i], val - end)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | class Solution {
public long maxEarnings(int[][] meetings) {
int n = meetings.length;
Arrays.sort(meetings, (a, b) -> a[1] - b[1]);
long[] preMax = new long[n + 1];
Arrays.fill(preMax, Long.MIN_VALUE / 2);
long ans = 0;
for (int i = 0; i < n; i++) {
int start = meetings[i][0];
int end = meetings[i][1];
int revenue = meetings[i][2];
long val = revenue;
if (start >= meetings[0][1]) {
int j = upperBound(meetings, start, i);
val += preMax[j] + start;
}
ans = Math.max(ans, val);
preMax[i + 1] = Math.max(preMax[i], val - end);
}
return ans;
}
private int upperBound(int[][] meetings, int target, int hi) {
int l = 0, r = hi;
while (l < r) {
int m = (l + r) >>> 1;
if (meetings[m][1] <= target) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
public:
long long maxEarnings(vector<vector<int>>& meetings) {
int n = meetings.size();
sort(meetings.begin(), meetings.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
vector<long long> preMax(n + 1, LLONG_MIN / 2);
long long ans = 0;
for (int i = 0; i < n; i++) {
int start = meetings[i][0];
int end = meetings[i][1];
int revenue = meetings[i][2];
long long val = revenue;
if (start >= meetings[0][1]) {
int j = upper_bound(meetings.begin(), meetings.begin() + i, start,
[](int x, const vector<int>& y) {
return x < y[1];
})
- meetings.begin();
val += preMax[j] + start;
}
ans = max(ans, val);
preMax[i + 1] = max(preMax[i], val - end);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | func maxEarnings(meetings [][]int) int64 {
n := len(meetings)
sort.Slice(meetings, func(i, j int) bool {
return meetings[i][1] < meetings[j][1]
})
preMax := make([]int64, n+1)
for i := range preMax {
preMax[i] = -1 << 60
}
var ans int64
for i, meeting := range meetings {
start, end, revenue := meeting[0], meeting[1], meeting[2]
val := int64(revenue)
if start >= meetings[0][1] {
j := sort.Search(i, func(j int) bool {
return meetings[j][1] > start
})
val += preMax[j] + int64(start)
}
ans = max(ans, val)
preMax[i+1] = max(preMax[i], val-int64(end))
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | function maxEarnings(meetings: number[][]): number {
const n = meetings.length;
meetings.sort((a, b) => a[1] - b[1]);
const preMax = new Array<number>(n + 1).fill(-Infinity);
let ans = 0;
for (let i = 0; i < n; i++) {
const start = meetings[i][0];
const end = meetings[i][1];
const revenue = meetings[i][2];
let val = revenue;
if (start >= meetings[0][1]) {
let l = 0;
let r = i;
while (l < r) {
const m = (l + r) >> 1;
if (meetings[m][1] <= start) {
l = m + 1;
} else {
r = m;
}
}
val += preMax[l] + start;
}
ans = Math.max(ans, val);
preMax[i + 1] = Math.max(preMax[i], val - end);
}
return ans;
}
|