单调性贪心 —— 游乐设施调度

题目描述

两类游乐设施（陆地、水上），每类各选一个，顺序不限。每个设施有开始时间和持续时间。完成后可以立即开始下一个（如果已开放）或等待。问最早完成时间。

第一次思路（暴力 O(nm)）

Q1 数据量小（n,m ≤ 100），直接双层循环枚举所有配对：

int earliestFinishTime(...) {
    int res = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 两种顺序分别算
            int t1 = max(landEnd[i], waterStart[j]) + waterDuration[j];  // 先陆地后水上
            int t2 = max(waterEnd[j], landStart[i]) + landDuration[i];   // 先水上后陆地
            res = min(res, min(t1, t2));
        }
    }
    return res;
}

卡住了：数据变大到 5e4

Q2 的数据范围变成 5e4，O(nm) 会直接超时。

第一个可行方案：排序 + 二分 + 前后缀预处理

以”先陆地后水上”为例。固定一个陆地设施，它的结束时间 landEnd = landStart + landDuration。在这个基础上，水上设施的完成时间是：

waterFinish = max(landEnd, waterStart) + waterDuration

把所有水上设施按 waterStart 升序排序后，对于给定的 landEnd，二分找到第一个 start ≥ landEnd 的分界点 p：

• 左侧（start < landEnd）：必须等到 landEnd 才能开始 → 完成时间 = landEnd + duration。这部分只关心最小的 duration，所以预处理 前缀最小持续时间 preMinDur。
• 右侧（start ≥ landEnd）：可以直接开始 → 完成时间 = start + duration。这部分只关心最小的 start + duration，所以预处理 后缀最小结束时间 sufMinEnd。

这样对每个陆地设施，O(log m) 就能算出最优配对，总复杂度 O(n log m + m log n)。

实现中的几个坑

① 预处理数组要基于排序后的数组

排序后 waterPair 的下标变了，preMinDur 和 sufMinEnd 必须基于排序后的数组构建，不能用原始数组索引。

② 二分的右边界取 size() 不是 size()-1

当所有水上设施的 start 都小于 landEnd 时，分界点 p 应该等于 m（表示”右侧为空”）。用闭区间 [0, size-1] 永远返回不了 m，所以要用半开区间 [0, size)：

int lowerBound(vector<pair<int, int>>& arr, int target) {
    int l = 0, r = arr.size();      // r = size，不是 size-1
    while (l < r) {
        int m = (l + r) / 2;
        if (arr[m].first < target) l = m + 1;
        else r = m;
    }
    return l;  // 可能返回 size（全部小于 target）
}

③ 取值时判断越界

当 p == 0 时，左侧为空，只能用 sufMinEnd[0]。当 p == m 时，右侧为空，只能用 landEnd + preMinDur[m-1]：

int p = lowerBound(waterPair, landEnd);
if (p > 0) time = min(time, landEnd + preMinDur[p - 1]);  // 左侧存在
if (p < m) time = min(time, suMinEnd[p]);                 // 右侧存在

完整代码（排序 + 二分 + 预处理方案）

class Solution {
    int lowerBound(vector<pair<int, int>>& arr, int target) {
        int l = 0, r = arr.size();
        while (l < r) {
            int m = (l + r) / 2;
            if (arr[m].first < target) l = m + 1;
            else r = m;
        }
        return l;
    }

public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration,
                           vector<int>& waterStartTime, vector<int>& waterDuration) {
        int n = landStartTime.size(), m = waterStartTime.size();

        // 构建 pair 并排序
        vector<pair<int, int>> landPair(n), waterPair(m);
        for (int i = 0; i < n; i++) landPair[i] = {landStartTime[i], landDuration[i]};
        for (int j = 0; j < m; j++) waterPair[j] = {waterStartTime[j], waterDuration[j]};
        ranges::sort(landPair);
        ranges::sort(waterPair);

        // 先陆地后水上 — 基于 waterPair 预处理
        vector<int> preMinDur(m), sufMinEnd(m);
        int minDur = waterPair[0].second;
        for (int j = 0; j < m; j++) {
            minDur = min(minDur, waterPair[j].second);
            preMinDur[j] = minDur;
        }
        int minEnd = waterPair[m - 1].first + waterPair[m - 1].second;
        for (int j = m - 1; j >= 0; j--) {
            minEnd = min(minEnd, waterPair[j].first + waterPair[j].second);
            sufMinEnd[j] = minEnd;
        }
        int best = INT_MAX;
        for (auto& [s, d] : landPair) {
            int landEnd = s + d;
            int p = lowerBound(waterPair, landEnd);
            if (p > 0) best = min(best, landEnd + preMinDur[p - 1]);
            if (p < m) best = min(best, sufMinEnd[p]);
        }
        int landToWater = best;

        // 先水上后陆地 — 基于 landPair 预处理（对称，略）
        // ...

        return min(landToWater, waterToLand);
    }
};

这个方案能过，但写了快 60 行，而且不少细节（二分边界、预处理下标）一不注意就写错。

真正的突破：发现了单调性

我后来看到一个更短的解法，看第一遍的时候觉得”这也太简单了吧”。但仔细推了它的逻辑之后发现——它之所以简单，是因为发现了目标函数的单调性。

以”先陆地后水上”为例，完成时间公式：

finish = max(landEnd, waterStart) + waterDuration

对于一个固定的水上设施，waterDuration 是常数，landEnd 越大，max(landEnd, waterStart) 只会变大或不变。

所以不管选哪个水上设施，landEnd 都是越小越好。 那陆地设施直接选最早完成的 min(start + duration) 就行了，根本不需要枚举！

在这个最早完成的陆地上，再遍历水上设施，找最小的 max(waterStart, landEnd_best) + waterDuration，就得到了”先陆地后水上”的最优解。

对称地，”先水上后陆地”同理。

最终代码

class Solution {
    int solve(vector<int>& start1, vector<int>& duration1,
              vector<int>& start2, vector<int>& duration2) {
        // 第一类：最早完成时间
        int finish1 = INT_MAX;
        for (int i = 0; i < start1.size(); i++) {
            finish1 = min(finish1, start1[i] + duration1[i]);
        }
        // 第二类：以此为基础的最小完成时间
        int finish2 = INT_MAX;
        for (int i = 0; i < start2.size(); i++) {
            finish2 = min(finish2, max(start2[i], finish1) + duration2[i]);
        }
        return finish2;
    }

public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration,
                           vector<int>& waterStartTime, vector<int>& waterDuration) {
        return min(solve(landStartTime, landDuration, waterStartTime, waterDuration),
                   solve(waterStartTime, waterDuration, landStartTime, landDuration));
    }
};

复杂度分析

复杂度	分析
时间复杂度	O(n + m) —— 每种顺序两次线性遍历
空间复杂度	O(1)

心得总结

二分 + 前后缀预处理方案本身没有问题，但在它之前应该先检查目标函数是否有单调性——如果 max(landEnd, waterStart) + dur 中 landEnd 越小越好，那直接贪心就完事了，根本不需要那些数据结构。