登录排序 + 单调栈二分（Python/Java/C++/Go）
设参加的第二个活动的开始时间为 $\textit{startTime}$，那么第一个活动选哪个最好？
在结束时间小于 $\textit{startTime}$ 的活动中，选择价值最大的活动。
为了方便查找，先把 $\textit{events}$ 按照结束时间从小到大排序。
排序后，对比如下两个活动：
- 活动一：结束于 $3$ 时刻，价值 $999$。
- 活动二：结束于 $6$ 时刻，价值 $9$。
活动二的结束时间又晚，价值又小，全方面不如活动一，是垃圾数据，直接忽略。
换句话说，在遍历 $\textit{events}$ 的过程中（注意 $\textit{events}$ 已按照结束时间排序），只在遇到更大价值的活动时，才记录该活动。把这些活动记录到一个栈（列表）中，那么从栈底到栈顶，结束时间是递增的，价值也是递增的，非常适合二分查找。关于二分查找的原理，请看 二分查找 红蓝染色法【基础算法精讲 04】。
枚举第二个活动，在单调栈中二分查找结束时间严格小于 $\textit{startTime}$ 的最后一个活动，即为价值最大的第一个活动。如果没找到，那么只能选一个活动。
为了简化判断逻辑，可以在栈底加一个结束时间为 $0$，价值也为 $0$ 的哨兵。
写法一
class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
# 按照结束时间排序
events.sort(key=lambda e: e[1])
# 从栈底到栈顶，结束时间递增，价值递增
st = [(0, 0)] # 栈底哨兵
ans = 0
for start_time, end_time, value in events:
# 二分查找最后一个结束时间 < start_time 的活动
i = bisect_left(st, (start_time,)) - 1
ans = max(ans, st[i][1] + value)
# 遇到比栈顶更大的价值，入栈
if value > st[-1][1]:
st.append((end_time, value))
return ans
class Solution {
public int maxTwoEvents(int[][] events) {
// 按照结束时间排序
Arrays.sort(events, (a, b) -> a[1] - b[1]);
// 从栈底到栈顶，结束时间递增，价值递增
ArrayList<int[]> st = new ArrayList<>(); // (结束时间, 价值)
st.add(new int[]{0, 0}); // 栈底哨兵
int ans = 0;
for (int[] e : events) {
int i = search(st, e[0]);
int value = e[2];
ans = Math.max(ans, st.get(i)[1] + value);
// 遇到比栈顶更大的价值，入栈
if (value > st.getLast()[1]) {
st.add(new int[]{e[1], value});
}
}
return ans;
}
// 返回最后一个满足 st[i][0] < target 的 i
private int search(List<int[]> st, int target) {
int left = -1, right = st.size();
while (left + 1 < right) { // 开区间二分
int mid = left + (right - left) / 2;
if (st.get(mid)[0] < target) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
// 按照结束时间排序
ranges::sort(events, {}, [](auto& e) { return e[1]; });
// 从栈底到栈顶，结束时间递增，价值递增
vector<pair<int, int>> st = {{0, 0}}; // 栈底哨兵
int ans = 0;
for (auto& e : events) {
int start_time = e[0], value = e[2];
// 二分查找最后一个结束时间 < start_time 的活动
auto it = --ranges::lower_bound(st, start_time, {}, &pair<int, int>::first);
ans = max(ans, it->second + value);
// 遇到比栈顶更大的价值，入栈
if (value > st.back().second) {
st.emplace_back(e[1], value);
}
}
return ans;
}
};
func maxTwoEvents(events [][]int) (ans int) {
// 按照结束时间排序
slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })
// 从栈底到栈顶，结束时间递增，价值递增
type pair struct{ endTime, value int }
st := []pair{{}} // 栈底哨兵
for _, e := range events {
startTime, value := e[0], e[2]
// 二分查找最后一个结束时间 < startTime 的活动
i := sort.Search(len(st), func(i int) bool { return st[i].endTime >= startTime }) - 1
ans = max(ans, st[i].value+value)
// 遇到比栈顶更大的价值，入栈
if value > st[len(st)-1].value {
st = append(st, pair{e[1], value})
}
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
写法二：原地
也可以把 $\textit{events}$ 当作栈。
缺点是没法用哨兵。
class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda e: e[1])
ans = size = 0 # 把 events 当作栈
for start_time, end_time, value in events:
i = bisect_left(events, (start_time,), hi=size) - 1
if i >= 0:
ans = max(ans, value + events[i][1])
else:
ans = max(ans, value)
if size == 0 or value > events[size - 1][1]:
events[size] = (end_time, value)
size += 1
return ans
class Solution {
public int maxTwoEvents(int[][] events) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
int ans = 0;
int size = 0; // 把 events 当作栈
for (int[] e : events) {
int i = search(events, size, e[0]);
int value = e[2];
if (i >= 0) {
ans = Math.max(ans, value + events[i][2]);
} else {
ans = Math.max(ans, value);
}
if (size == 0 || value > events[size - 1][2]) {
events[size++] = e;
}
}
return ans;
}
// 返回最后一个满足 st[i][1] < target 的 i
private int search(int[][] st, int right, int target) {
int left = -1;
while (left + 1 < right) { // 开区间二分
int mid = left + (right - left) / 2;
if (st[mid][1] < target) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
ranges::sort(events, {}, [](auto& e) { return e[1]; });
int ans = 0, size = 0; // 把 events 当作栈
for (auto& e : events) {
int start_time = e[0], value = e[2];
auto it = ranges::lower_bound(events.begin(), events.begin() + size, start_time, {}, [](auto& e) { return e[1]; });
if (it != events.begin()) {
ans = max(ans, value + (*--it)[2]);
} else {
ans = max(ans, value);
}
if (size == 0 || value > events[size - 1][2]) {
events[size++] = e;
}
}
return ans;
}
};
func maxTwoEvents(events [][]int) (ans int) {
slices.SortFunc(events, func(a, b []int) int { return a[1] - b[1] })
st := events[:0] // 把 events 当作栈
for _, e := range events {
startTime, value := e[0], e[2]
i := sort.Search(len(st), func(i int) bool { return st[i][1] >= startTime }) - 1
if i >= 0 {
ans = max(ans, value+events[i][2])
} else {
ans = max(ans, value)
}
if len(st) == 0 || value > st[len(st)-1][2] {
st = append(st, e)
}
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{events}$ 的长度。
- 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。
专题训练
- 单调栈题单。
- 动态规划题单的「§7.2 不相交区间」。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
