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

结束于 5、开始于 5，凭什么也算重叠

每个活动给三个数：开始、结束、价值。最多挑两个参加，求价值之和最大，只挑一个也行。规则里埋着一个等号：开始和结束两个时刻都算占用——结束于 5、另一个从 5 开始，就在时刻 5 撞上，后者至少从 6 开始才接得上。写成条件就是后一个的开始必须严格大于前一个的结束，差一个等号，合法性完全两样。

活动两两硬配，为什么 n 一大就试不完

n 个活动两两配成对约有 n²/2 种，几万个活动就是十亿量级，逐对查重叠、算价值和，跑不完（O(n²)，大 O 描述数据量变大时操作次数怎么涨）。慢的根子是同一个数被重算了 n 遍：固定一个活动后，真正想知道的只有一件事——在它结束之后才开始的那批活动里，最大价值是多少。提前存好就省了。

f 这一列为什么要从最后一行倒着填

先按开始时间从小到大排序，把排序后的活动列成表、一行一个活动。某个活动的开始一旦大于我的结束，排它后面的活动也都大于——能接上的搭档连成一段尾巴。尾巴里只关心价值最高的那个，于是定义后缀最大值 f[i]（从第 i 行起到最后一行，价值最大是多少）。

这是一小段动态规划（先把『第 i 行往下价值最高是多少』逐行填好，配对时直接查）：f[i]=max(f[i+1], 本行价值)，每格依赖下一格，只能从最后一行倒着往上填，最后一行的 f 就是它自己的价值。

每个活动的搭档，为什么二分一次就锁定

『开始大于我的结束』在排好的数组里从某一行起整段成立，一刀切的分界正适合二分（每次看中间那行、一半一半排除的查找法），找出第一个开始严格大于当前结束的下标 idx，f[idx] 加本活动价值就是以它打头的最好组合。idx 越界说明谁都接不上，本活动单独参加，裸价值也参与取最大，『只选一个』就这么算进去了。

拿题面三个活动，亲手把 4 算出来

用题面第一组 events=[[1,3,2],[4,5,2],[2,4,3]]。按开始排序得 [[1,3,2],[2,4,3],[4,5,2]]。倒着填 f（下标从 0 数起）：f[2]=2；f[1]=max(2,3)=3；f[0]=max(3,2)=3，f=[3,3,2]。

逐个配对：[1,3,2] 结束于 3，第一个开始大于 3 的是下标 2 的 [4,5,2]，得 2+f[2]=2+2=4；[2,4,3] 结束于 4，下标 2 的开始是 4，不严格大于 4，接不上，单独算 3；[4,5,2] 结束于 5，后面没人，单独算 2。候选 4、3、2 取最大，答案 4，题面给的也是 4。

边界写成大于等于，5 分为什么会冒出来

二分条件一旦写成大于等于，[2,4,3] 就会接上开始于 4 的 [4,5,2]，得 3+2=5——多出的 1 分来自时刻 4 被占两次的非法组合。f 的方向也别弄错，f[i] 靠 f[i+1] 推，从上往下填拿到的全是没算好的值；二分还依赖排序，没排就没有整段分界可找。

排序 O(n log n) 是大头，填 f 一趟 O(n)，逐活动二分共 O(n log n)，合计 O(n log n)；额外一列 f，空间 O(n)。

Python

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

C++

#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;
    }
};

Java

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;
    }
}