2054. 两个最好的不重叠活动

发表于 2026-01-12 更新于 2026-01-13 分类于力扣阅读次数： Waline：本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

时间戳
状态机DP
划分DP
二分
排序

思路

一、问题回顾（统一抽象）

给定若干事件 \[ \text{event}_i = (s_i, e_i, v_i) \] 其中：

\(s_i\)：开始时间
\(e_i\)：结束时间
\(v_i\)：事件价值

要求从中选择 最多两个 事件，使得： \[ e_a < s_b \quad \text{或} \quad e_b < s_a \] 并最大化所选事件价值之和。

二、建模视角一：时间轴扫描（Timestamp / Sweep Line）

2.1 核心思想

该方法不直接在“事件集合”上做选择，而是把问题投影到时间轴上，将每个事件拆解为：

一个「开始节点」
一个「结束节点」

然后按时间顺序扫描，动态维护：

当前时间之前 已结束事件的最大价值
当前时间开始的事件，尝试与此前最佳事件配对

本质上，这是一个 时间轴上的贪心扫描问题。

2.2 数据结构设计

对每个事件 \((s, e, v)\)，构造两个节点：

op	t	v	含义
0	s	v	事件开始
1	e	v	事件结束

并按如下规则排序：

时间 \(t\) 升序
同一时间，开始节点在前，结束节点在后

2.3 扫描过程的状态定义

mx：当前时间点之前，所有已经结束事件的最大价值
ans：全局答案

扫描每个节点：

若是开始节点 (op = 0) → 可以与此前结束的最佳事件配对，更新： \[ ans = \max(ans, v + mx) \]
若是结束节点 (op = 1) → 更新： \[ mx = \max(mx, v) \]

2.4 正确性直觉

时间轴扫描保证了 所有已结束事件一定不与当前开始事件重叠
mx 始终代表“在当前时间之前可选的最优单事件”
每个事件只被处理一次，时间复杂度为 \(O(n \log n)\)

2.5 代码实现（带注释）

class Solution {
 public:
  // 时间轴上的节点
  struct node {
    int op; // 0: start, 1: end
    int t;  // time
    int v;  // value
  };

  // 按时间排序；同一时间 start 在前
  struct cmp {
    bool operator()(node& x, node& y) {
      if (x.t != y.t) return x.t < y.t;
      return x.op < y.op;
    }
  };

  int maxTwoEvents(vector<vector<int>>& events) {
    vector<node> arr;

    // 拆分每个事件为开始点和结束点
    for (auto& event : events) {
      arr.push_back({0, event[0], event[2]}); // start
      arr.push_back({1, event[1], event[2]}); // end
    }

    sort(arr.begin(), arr.end(), cmp());

    int ans = 0; // 最终答案
    int mx = 0;  // 已结束事件中的最大价值

    // 扫描时间轴
    for (auto& [op, t, v] : arr) {
      if (op == 0) {
        // 当前事件开始，尝试与之前结束的最优事件配对
        ans = max(ans, v + mx);
      } else {
        // 当前事件结束，更新已结束事件的最大值
        mx = max(mx, v);
      }
    }
    return ans;
  }
};

2.6 方法特点总结

优点

思路简洁
无需 DP、二分
实现短小，常数极小

局限

强依赖“最多选两个”这一限制
不易扩展到选 \(k\) 个事件的情形

三、建模视角二：状态机动态规划（Interval DP）

3.1 核心思想

该方法从“事件集合”的角度建模问题，将其视为一个带冲突约束的区间选择问题。

事件按结束时间排序后，可以进行如下状态划分：

在前 \(i\) 个事件中，已经选择了 \(k\) 个事件的最大价值。

3.2 状态定义

排序后事件编号为 \(1 \dots n\)。

定义 DP： \[ \begin{aligned} f_1[i] &: \text{在前 } i \text{ 个事件中，最多选 1 个的最大价值} \\ f_2[i] &: \text{在前 } i \text{ 个事件中，最多选 2 个的最大价值} \end{aligned} \]

3.3 转移关键：不重叠前驱

对于事件 \(i\)，需要找到： \[ p(i) = \max \{ j < i \mid e_j < s_i \} \] 即最后一个与事件 \(i\) 不冲突的事件编号。

由于事件按结束时间排序，可通过二分搜索得到。

3.4 状态转移方程

\[ \begin{aligned} f_1[i] &= \max(f_1[i-1], v_i) \\ f_2[i] &= \max(f_2[i-1], f_1[p(i)] + v_i) \end{aligned} \]

3.5 代码实现（带注释）

class Solution {
public:
    // 按结束时间排序
    struct cmp {
        bool operator()(vector<int>& x, vector<int>& y) {
            if (x[1] != y[1])
                return x[1] < y[1];
            return x[0] < y[0];
        }
    };

    // 在 events[0..i-2] 中寻找最后一个 end < k 的位置
    int search(int k, int i, vector<vector<int>>& events) {
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (events[mid - 1][1] <= k - 1)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }

    int maxTwoEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp());
        int n = events.size();

        // f[1][i]: 前 i 个事件中选 1 个的最大值
        // f[2][i]: 前 i 个事件中选 2 个的最大值
        static int f[3][100005];

        f[1][0] = 0;
        f[2][0] = INT_MIN >> 1;

        for (int i = 1; i <= n; ++i) {
            int s = events[i - 1][0];
            int v = events[i - 1][2];

            // 找到最后一个不冲突的事件
            int pre = search(s, i, events);

            // 状态转移
            f[2][i] = max(f[2][i - 1], f[1][pre] + v);
            f[1][i] = max(f[1][i - 1], v);
        }
        return max(f[1][n], f[2][n]);
    }
};

3.6 方法特点总结

优点

建模清晰、可扩展
易推广到「选 \(k\) 个不重叠区间」
属于经典区间 DP 框架

缺点

实现复杂度更高
需要排序 + 二分
常数略大于时间轴扫描