两个最好的不重叠活动 图解题解

这道题到底在问什么

输入

events=[[1,3,2],[4,5,2],[2,4,3]]

输出

4 (选活动 [1,3,2] 与 [4,5,2],2 加 2)

输入

events=[[1,5,3],[1,5,1],[6,6,5]]

输出

8 (选 [1,5,3] 与 [6,6,5],3 加 5)

最优解：一步一步想明白

1. 3记牢这套:排序,填后缀最大值 f,再逐个活动找第一个开得下的边界、用本价值加边界处的 f。下面按这套一步步填表。
2. 4五个活动待处理先把五个活动摊成一张表,每一行是一个活动,列从左到右是开始、结束、价值,右边两列 f 和配对是我们待会儿要算的辅助值,现在先空着。左边那一列是活动的名字 A 到 E。你看开始时间这一列是 3,1,6,2,4,乱的,第一步得把它排好。
3. 5已按开始升序按开始时间从小到大排一遍。现在左边活动名的顺序变成了 B、D、A、E、C,开始时间这一列(绿色)是 1、2、3、4、6,规规矩矩升序。排序这一步很关键:排好之后,只要某个活动的开始时间大于我的结束时间,它以及它下面所有活动的开始时间都大于我的结束,天然接得上,后面找边界才能一刀切。
4. 6辅助列待填正式开算前,先说清右边两列是干嘛的。f 这一列,表示从这一行往下、价值最高的活动值多少,它帮我们一眼看出结束之后能接的最好活动。配对这一列,是把本活动价值,加上它结束后能接的那个最优价值,得到以这个活动打头的最好组合。两列都从下往上、从上往下分两趟填,先填 f。
5. 7f 填到第 5 行从最后一行活动 C 开始填 f。它下面没有别人了,所以从它往下价值最大的就是它自己,f 记成它的价值 6。
6. 8f 填到第 4 行往上填活动 E 这一行的 f。比较两个数:下面一行的 f 是 6,本行自己的价值是 3,谁大取谁,f = 6。下面已经有更高价值的活动,f 沿用 6。
7. 9f 填到第 3 行往上填活动 A 这一行的 f。比较两个数:下面一行的 f 是 6,本行自己的价值是 7,谁大取谁,f = 7。本行价值更大,f 被自己刷新了。
8. 10f 填到第 2 行往上填活动 D 这一行的 f。比较两个数:下面一行的 f 是 7,本行自己的价值是 5,谁大取谁,f = 7。下面已经有更高价值的活动,f 沿用 7。
9. 11f 填到第 1 行往上填活动 B 这一行的 f。比较两个数:下面一行的 f 是 7,本行自己的价值是 4,谁大取谁,f = 7。下面已经有更高价值的活动,f 沿用 7。
10. 12f 列就绪f 这一列填完了,从上到下是 7、7、7、6、6。它的含义再强调一遍:比如第四行 E 的 f 是 6,意思是从 E 往下(也就是 E 和 C 里)价值最高的是 6。有了这一列,任何活动只要知道结束后从哪一行接得上,就能立刻查出那之后能拿的最高价值。接下来逐个活动算配对。
11. 13为 B 找搭档轮到活动 B 当打头的,它结束于 2。往下找第一个开始时间严格大于 2 的活动,是活动 A,它的开始是 3(紫色是本活动结束,黄色是接得上的分界)。从这一行往下的活动都不会和 B 撞。
12. 14B 配对 = 11接得上就好办了。从分界那一行往下最高价值就是那行的 f,等于 7。用 B 自己的价值 4 加上 7,配对总价值是 11(绿色),记到配对列。目前所有配对里最大的是 11。
13. 15为 D 找搭档轮到活动 D 当打头的,它结束于 4。往下找第一个开始时间严格大于 4 的活动,是活动 C,它的开始是 6(紫色是本活动结束,黄色是接得上的分界)。从这一行往下的活动都不会和 D 撞。
14. 16D 配对 = 11接得上就好办了。从分界那一行往下最高价值就是那行的 f,等于 6。用 D 自己的价值 5 加上 6,配对总价值是 11(绿色),记到配对列。目前所有配对里最大的是 11。
15. 17为 A 找搭档轮到活动 A 当打头的,它结束于 5。往下找第一个开始时间严格大于 5 的活动,是活动 C,它的开始是 6(紫色是本活动结束,黄色是接得上的分界)。从这一行往下的活动都不会和 A 撞。
16. 18A 配对 = 13接得上就好办了。从分界那一行往下最高价值就是那行的 f,等于 6。用 A 自己的价值 7 加上 6,配对总价值是 13(绿色),记到配对列。目前所有配对里最大的是 13。
17. 19为 E 找搭档轮到活动 E 当打头的,它结束于 6。可它已经排在很后面,下面再没有哪个活动的开始时间大于 6 了,谁都接不上。那它只能单独参加。
18. 20E 配对 = 3接不上,活动 E 只能自己参加,配对总价值就是它自己的价值 3(绿色)。目前所有配对里最大的仍是 13。
19. 21为 C 找搭档轮到活动 C 当打头的,它结束于 7。可它已经排在很后面,下面再没有哪个活动的开始时间大于 7 了,谁都接不上。那它只能单独参加。
20. 22C 配对 = 6接不上,活动 C 只能自己参加,配对总价值就是它自己的价值 6(绿色)。目前所有配对里最大的仍是 13。
21. 23答案 = 13五个活动的配对都算完了,配对这一列从上到下是 11、11、13、3、6。里头最大的是 13,出现在活动 A 那一行(绿色)。这个 13 就是最终答案。
22. 24最优 = 13把这个 13 拆开看是谁凑的。打头的是活动 A,开始 3 结束 5,价值 7;它结束于 5,接上开始于 6 的活动 C,价值 6。两段时间不碰,价值 7 加 6 等于 13,这就是最优组合。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort()
        n = len(events)
        f = [events[-1][2]] * n
        for i in range(n - 2, -1, -1):
            f[i] = max(f[i + 1], events[i][2])
        ans = 0
        for _, e, v in events:
            idx = bisect_right(events, e, key=lambda x: x[0])
            if idx < n:
                v += f[idx]
            ans = max(ans, v)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        int n = events.size();
        vector<int> f(n + 1);
        for (int i = n - 1; ~i; --i) {
            f[i] = max(f[i + 1], events[i][2]);
        }
        int ans = 0;
        for (const auto& e : events) {
            int v = e[2];
            int left = 0, right = n;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (events[mid][0] > e[1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (left < n) {
                v += f[left];
            }
            ans = max(ans, v);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int n = events.length;
        int[] f = new int[n + 1];
        for (int i = n - 1; i >= 0; --i) {
            f[i] = Math.max(f[i + 1], events[i][2]);
        }
        int ans = 0;
        for (int[] e : events) {
            int v = e[2];
            int left = 0, right = n;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (events[mid][0] > e[1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (left < n) {
                v += f[left];
            }
            ans = Math.max(ans, v);
        }
        return ans;
    }
}

复杂度

面试官可能追问