What is the core pattern for solving Two Best Non-Overlapping Events?

The main pattern is state transition dynamic programming combined with sorting and binary search to efficiently find non-overlapping events.

Why do we sort events by end time rather than start time?

Sorting by end time allows binary search to quickly find the last non-overlapping event for combining maximum values.

Can this approach handle more than two events?

Yes, by extending the DP to track multiple event combinations, though the logic becomes more complex and may require segment trees or k-DP.

How does inclusive time affect event selection?

Inclusive times mean if one event ends at t, the next cannot start at t; it must start at t + 1 or later, which prevents accidental overlap.

What common mistake should I avoid in this problem?

A frequent mistake is checking only start < end instead of accounting for the inclusive boundary rule, leading to invalid overlapping selections.

#2054

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

两个最好的不重叠活动

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTime i , endTime i , value i ] 。第 i 个活动开始于 startTime i ，结束于 endTime i ，如果你参加这个活动，那么你可以得到价值 value i 。你…

数组二分查找动态规划排序堆（优先队列）

题目描述

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTime_i, endTime_i, value_i] 。第 i 个活动开始于 startTime_i ，结束于 endTime_i ，如果你参加这个活动，那么你可以得到价值 value_i 。你最多可以参加 两个时间不重叠 活动，使得它们的价值之和最大。

请你返回价值之和的 最大值 。

注意，活动的开始时间和结束时间是包括在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]
输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

Example 1 Diagram

输入：events = [[1,3,2],[4,5,2],[1,5,5]]
输出：5
解释：选择活动 2 ，价值和为 5 。

示例 3：

输入：events = [[1,5,3],[1,5,1],[6,6,5]]
输出：8
解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

提示：

2 <= events.length <= 10⁵
events[i].length == 3
1 <= startTime_i <= endTime_i <= 10⁹
1 <= value_i <= 10⁶

lightbulb

解题思路

方法一：排序 + 二分查找

我们可以讲活动按照开始排序，然后预处理出以每个活动为作为开始的最大价值，即 $f[i]$ 表示从第 $i$ 个活动开始，到最后一个活动结束，选择其中一个活动的最大价值。

然后我们枚举每个活动，对于每个活动，我们使用二分查找找到第一个开始时间大于当前活动结束时间的活动，下标记为 $\textit{idx}$ ，那么以当前活动为开始的最大价值就是 $f[\textit{idx}]$ ，加上当前活动的价值，即为以当前活动为第一个活动，最终能获得的最大价值。求最大值即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为活动的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	O(n \cdot \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Sorting by end times can simplify non-overlapping checks.
question_mark
Using a DP array to store one-event maxima shows clear state transition understanding.
question_mark
Binary search integration reveals awareness of combining past results efficiently.

warning

常见陷阱

外企场景

error
Failing to account for inclusive end times and start times leading to overlap errors.
error
Not storing the best single-event value up to each index, which makes combining events inefficient.
error
Attempting a naive O(n^2) comparison between all pairs of events, exceeding time limits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximizing sum for at most k non-overlapping events instead of two.
arrow_right_alt
Events with weighted durations where value per unit time must be maximized.
arrow_right_alt
Allowing overlapping events with a penalty to combine values differently.

help

常见问题

外企场景

继续练习

#2008 出租车的最大盈利 #1851 包含每个查询的最小区间 #2333 最小差值平方和