leetcode 2589

题解

typedef pair<int, int> PII;

const int N = 2010;
int dist[N];
bool st[N];

class Solution {
public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        int n = tasks.size();
        unordered_map<int, vector<PII>> graph;
        int ub = 0;
        for(int i = 0; i < n; i++){
            int a = tasks[i][0], b = tasks[i][1], c = tasks[i][2];
            // s[b]>=s[a-1]+c
            graph[a - 1].push_back({b, c});
            ub = max(ub, b);
        }
        for(int i = 1; i <= ub; i++) {
            // s[i]>=s[i-1]
            graph[i - 1].push_back({i, 0});
            // s[i]-s[i-1]<=1 -> s[i-1]>=s[i]-1
            graph[i].push_back({i - 1, -1});
        }
        spfa(graph);
        return dist[ub];
    }

private:
    void spfa(unordered_map<int, vector<PII>>& graph)  {
        queue<int> q;
        memset(dist, -0x3f, sizeof dist);
        dist[0] = 0;
        q.push(0);
        st[0] = true;
        while(!q.empty()) {
            int t = q.front();
            q.pop();
            st[t] = false;
            for(auto&tup: graph[t]) {
                int j = tup.first, w = tup.second;
                if(dist[j] < dist[t] + w) {
                    dist[j] = dist[t] + w;
                    if(!st[j]) {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
};

要彻底搞懂这道题的差分约束+SPFA求最长路解法，我们需要从问题本质→数学转化→差分约束原理→建边逻辑→算法实现一步步拆解，哪怕你完全不懂差分约束，也能跟着这个逻辑吃透每一个细节。

一、先把原问题说透

题目要求：构造一个整数集合$Z$，使得对于每个区间$[a_i, b_i]$，$Z$中落在这个区间里的数至少有$c_i$个。最终要让$Z$的元素个数最少。

举个简单例子：比如有1个区间$[2,5]$，$c_i=3$。那么$Z$里至少要在2~5中选3个数，比如选{2,3,4}，此时$Z$的大小是3，这就是最小解。

核心难点：如何把“区间内至少选$c_i$个数”的约束，转化为可计算的数学关系？

二、关键转化：前缀和定义$s_i$

为了把区间约束转化为两个点的差值约束，我们引入前缀和数组$s$，这是整个解法的核心桥梁： 定义$s_i$表示：从整数1到i中，被选入集合$Z$的数的个数。

比如：

• $s_0$：表示1到0（空集）中选的数的个数，显然$s_0=0$（这是基准值，非常重要）；
• $s_3$：表示1、2、3中被选入$Z$的数的个数；
• 区间$[a_i, b_i]$内被选的数的个数 = $s_{b_i} - s_{a_i-1}$（前缀和的基本性质：区间和=右端点前缀和 - 左端点前一个的前缀和）。

题目中“区间$[a_i, b_i]$内至少选$c_i$个数”的约束，就可以转化为：

$$s_{b_i} - s_{a_i-1} \geq c_i$$

这一步是把实际问题转化为数学不等式的关键，也是差分约束的入口。

三、先补基础：差分约束系统的核心原理

在讲后续的约束条件前，必须先搞懂差分约束是什么、为什么能转化为图的最长路/最短路。

1. 差分约束系统的定义

由一组形如$x_j - x_i \geq w$（或$x_j - x_i \leq w$）的不等式组成的系统，称为差分约束系统。我们的目标是找到满足所有不等式的一组变量值。

2. 与图论的关联（核心！）

差分约束的求解依赖于最短路/最长路的松弛性质，这是建边的根本依据：

• 对于最短路：在图中，从节点$i$到$j$有一条权值为$w$的边，那么最短路的松弛条件是：

  $$dist[j] \leq dist[i] + w$$

  对应不等式：$x_j \leq x_i + w$（即$x_j - x_i \leq w$）。
• 对于最长路：在图中，从节点$i$到$j$有一条权值为$w$的边，那么最长路的松弛条件是：

  $$dist[j] \geq dist[i] + w$$

  对应不等式：$x_j \geq x_i + w$（即$x_j - x_i \geq w$）。

结论：

• 如果约束是$x_j \geq x_i + w$，则在图中添加一条**$i \to j$、权值为$w$的边，然后求最长路**；
• 如果约束是$x_j \leq x_i + w$，则在图中添加一条**$i \to j$、权值为$w$的边，然后求最短路**。

我们的题目中所有约束最终都会转化为$x_j \geq x_i + w$的形式，因此需要求最长路。

四、推导所有约束条件（建边的依据）

我们已经有了前缀和$s_i$，现在要根据实际意义，推导出所有关于$s$的不等式约束，再转化为图的边。

首先明确：我们需要考虑的$s$的下标范围是0到$ub$（$ub$是所有$b_i$中的最大值）。因为超过$ub$的数，选或不选都不会影响任何区间的约束（所有区间的右端点都不超过$ub$），因此只需考虑0~$ub$这些节点。

接下来推导3个核心约束：

约束1：$s_i \geq s_{i-1} + 0$（$i \geq 1$）

实际意义：$s_i$是1_{i中选的数的个数，$s_{i-1}$是1}i-1中选的数的个数。i这个数要么选（$s_i = s_{i-1}+1$），要么不选（$s_i = s_{i-1}$），因此$[1,i]$中选的数的个数至少等于$[1,i-1]$中的个数。

建边逻辑：根据差分约束的最长路规则，$s_i \geq s_{i-1} + 0$对应从节点$i-1$到节点$i$，连一条权值为0的边。

约束2：$s_{i-1} \geq s_i - 1$（$i \geq 1$）

实际意义：i这个数最多只能被选一次，因此$[1,i]$中选的数的个数，比$[1,i-1]$中最多多1个，即：

$$s_i - s_{i-1} \leq 1$$

将这个不等式移项，得到：

$$s_{i-1} \geq s_i + (-1)$$

建边逻辑：根据最长路规则，$s_{i-1} \geq s_i + (-1)$对应从节点$i$到节点$i-1$，连一条权值为-1的边。

约束3：$s_{b_i} \geq s_{a_i-1} + c_i$（题目核心约束）

实际意义：我们在第二部分已经推导过，区间$[a_i, b_i]$内选的数的个数是$s_{b_i} - s_{a_i-1}$，题目要求这个值至少为$c_i$，即：

$$s_{b_i} - s_{a_i-1} \geq c_i$$

移项后就是：

$$s_{b_i} \geq s_{a_i-1} + c_i$$

建边逻辑：根据最长路规则，对应从节点$a_i-1$到节点$b_i$，连一条权值为$c_i$的边。

五、虚拟源点与SPFA求最长路

我们已经把所有约束转化为了边，接下来需要用算法求最长路。这里有两个关键问题：为什么用SPFA？、虚拟源点的作用是什么？

1. 虚拟源点：节点0

我们的前缀和$s_0$是一个基准值，$s_0=0$（空集的选数个数为0）。这个节点0就是虚拟源点，原因是：

• 差分约束需要一个起点，从起点出发能到达所有节点，才能求出所有节点的最长路；
• 节点0可以通过约束1的边（$0→1$，权0）到达1，再从1到达2，依此类推，最终能遍历0~ub的所有节点，满足“起点可达所有节点”的要求。

2. 为什么用SPFA求最长路？

SPFA是一种基于队列优化的Bellman-Ford算法，原本用于求有负权边但无负环的图的最短路。我们这里用它求最长路，只需要修改松弛操作的逻辑即可。

选择SPFA的原因：

• 我们的图中存在权值为-1的边（约束2的边），普通的Dijkstra算法无法处理负权边（或最长路的正权边），而SPFA可以；
• 题目中的约束是有解的，因此图中不存在正环（如果有正环，最长路会无穷大，说明约束矛盾），SPFA可以正常求出最长路。

3. SPFA求最长路的核心调整

SPFA原本的最短路松弛操作是：

若$dist[j] > dist[i] + w(i→j)$，则更新$dist[j] = dist[i] + w(i→j)$，并将j入队。

求最长路时，只需把松弛操作反过来：

若$dist[j] < dist[i] + w(i→j)$，则更新$dist[j] = dist[i] + w(i→j)$，并将j入队。

4. 初始化与答案

• 初始化：$dist[0] = 0$（因为$s_0=0$，这是确定的基准值），其余$dist[i]$初始化为负无穷（求最长路时，初始值要尽可能小，才能被松弛操作更新）。
• 最终答案：$dist[ub]$（$ub$是所有$b_i$的最大值）。

为什么答案是$dist[ub]$？

• $s_{ub}$表示1~ub中选入Z的数的个数，而超过ub的数选了也没用（不会影响任何区间的约束），因此$Z$的最小大小就是$s_{ub}$；
• 我们通过最长路求出的$dist[ub]$，是满足所有约束的$s_{ub}$的最小值（因为差分约束的最长路解是满足所有$\geq$约束的最小解，刚好贴合“选数最少”的目标）。

六、举个例子验证（更直观）

假设题目输入： $n=1$，区间$[2,5]$，$c_i=3$。

步骤1：确定$ub=5$，需要考虑的节点是0、1、2、3、4、5。

步骤2：建边（只列关键边，约束1和2的边全量建）：

• 约束1（$s_i \geq s_{i-1}+0$）：0→1(0)、1→2(0)、2→3(0)、3→4(0)、4→5(0)；
• 约束2（$s_{i-1} \geq s_i-1$）：1→0(-1)、2→1(-1)、3→2(-1)、4→3(-1)、5→4(-1)；
• 约束3（$s_5 \geq s_1 +3$）：1→5(3)（因为$a_i=2$，$a_i-1=1$；$b_i=5$，$c_i=3$）。

步骤3：SPFA初始化：$dist[0]=0$，$dist[1~5]=-∞$。

步骤4：SPFA松弛过程（关键步骤）：

1. 起点0入队，弹出0，松弛1：$dist[1] = max(-∞, 0+0)=0$，1入队；
2. 弹出1，松弛2（0）：$dist[2]=max(-∞,0+0)=0$，2入队；松弛0（-1）：$dist[0]=max(0,0-1)=0$（无变化）；松弛5（3）：$dist[5]=max(-∞,0+3)=3$，5入队；
3. 后续松弛其他节点，但$dist[5]$最终稳定为3。

最终$dist[5]=3$，即Z的最小大小是3，和我们之前的例子一致，验证了解法的正确性。

七、总结所有细节

1. 问题转化：用前缀和$s_i$将区间约束转化为$s_{b_i}-s_{a_i-1}≥c_i$；
2. 约束推导：根据$s_i$的实际意义，推导出3个不等式约束；
3. 建边规则：将每个$x_j≥x_i+w$的约束转化为$i→j$、权值$w$的边；
4. 源点与初始化：以$s_0=0$为起点，$dist[0]=0$，其余为负无穷；
5. SPFA求最长路：修改松弛操作，求0到ub的最长路；
6. 答案：$dist[ub]$即为集合Z的最小大小。

整个过程的核心是**“实际问题→数学不等式→图论边→最长路求解”**的层层转化，而差分约束就是连接不等式和图论的桥梁，SPFA则是处理最长路的工具。