区间问题专题lyh's blog

这一次探讨区间问题，这大多是基于贪心算法的，在很多题目中都能用到。下面讨论仅限于闭区间，开区间只需稍作调整即可。

区间去重

去除区间中所有包含其它区间的区间。
按左端点排序，左端点相同就按右端点排序，然后用一个类似栈的东西维护。

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int l, r;

    bool operator<(Node &s) {
        if (l != s.l)return l < s.l;
        return r < s.r;
    }
} nd[2005];

vector<Node> vvp;
int q;

int main() {
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)scanf("%d%d", &nd[i].l, &nd[i].r);
    sort(nd + 1, nd + q + 1);
    for (int i = 1; i <= q; i++) {
        while (!vvp.empty() && vvp[vvp.size() - 1].r >= nd[i].r)vvp.pop_back();
        if (vvp.empty() || nd[i].l > vvp[vvp.size() - 1].l)vvp.push_back(nd[i]);
    }
    return 0;
}

区间完全覆盖问题

        给定一个区间和这个区间上的m个子区间，求其中尽量少的区间，使得它们的并集覆盖整个区间。
        算法:将各个区间的左端点升序排序;确定左值p，初始化p=0。从所有左端点小于等于左值的区间中选出右端点最大的一个，并加入集合，更新左值为右端点值+1。
贪心正确性证明:
        假设总区间[1，n]，分区间[a₁，b₁]，[a₂，b₂]，… ，[a_m，b_m]。规定f(x)表示覆盖[x，n]的最小区间数，则有状态转移方程:

$f(x)=\min\{1+f(b_k+1)\}，a_k\leq x\leq b_k$

显然f(x)是单调减的，所以取b_k的最大值，即有f(x)=1+f(b_t+1)，b_t是最大的一个。这样就把动态规划问题转化为贪心。
在题目保证有解的前提下，b_t一定是不小于x的，可知算法的正确性。

#include <iostream>
#include <algorithm>

using namespace std;

struct node {
    int l, r;

    bool operator<(node x) {
        return this->l < x.l;
    }
} op[50];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)cin >> op[i].l >> op[i].r;
    sort(op, op + m);
    int p = 0, i = 0, ans = 0;
    while (p < m) {
        int maxn = 0;
        while (op[i].l <= p)maxn = max(maxn, op[i].r), i++;//根据序列的有序性,i不必初始化为0,直接按上一次的继续即可
        p = maxn + 1;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

最大不相交区间问题

        给定一个区间和它的m个子区间，求尽量多的区间使得它们两两不相交。
        算法:将区间按右端点升序排序，对于一簇右端点相同的区间，取左端点最大一个加入集合(如果可以加入的话)，然后继续找后面右端点相同的区间簇。
贪心正确性证明:
        假设总区间[1，n]，分区间[a₁，b₁]，[a₂，b₂]，… ，[a_m，b_m]。规定f(x)表示[1，x]中的最大不相交区间数目，则有状态转移方程:
当x是某个区间右端点时:

$f(x)=\max\{1+f(a_k-1)\}，b_k=x$

否则:

$f(x)=f(p)，p=\max\{b_k\}，b_k<x$

显然f(x)是单调增的，那么在x是某个区间的右端点时即有f(x)=1+f(a_t-1)，a_t是最大的一个。这里也就是取左端点值最大的那一个区间。结合这个状态转移方程不难理解算法的正确性。

#include <iostream>
#include <algorithm>

using namespace std;

struct node {
    int l, r;

    bool operator<(node x) {
        return this->r < x.r;
    }
} op[50];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)cin >> op[i].l >> op[i].r;
    sort(op, op + m);
    int r = -1, l = op[0].l, ans = 0, last = op[0].r;
    //r是已知的最大f(x)对应的x的值,l是最大的左端点值,ans存放答案,last储存上一次的右端点值
    for (int i = 1; i < m; i++) {
        if (op[i].r != last) {//不是相同右端点值
            if (l > r)ans++, r = op[i - 1].r;//若可以加入,则加入并更新r
            last = op[i].r;
            l = op[i].l;
        } else l = max(l, op[i].l);//相同右端点值,取左端点最大值
    }
    if (l > r)ans++;//最后的一个也要加入
    cout << ans << endl;
    return 0;
}

区间选点问题

        给定一个区间和其上的m个子区间，取尽可能少的点使得每一个区间中都有至少一个点。
        算法:按右端点升序排列，依次取区间，若该区间中没有点，则将其右端点加入。
        证明略。

#include <iostream>
#include <algorithm>

using namespace std;

struct node {
    int l, r;

    bool operator<(node x) {
        return this->r < x.r;
    }
} op[50];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)cin >> op[i].l >> op[i].r;
    sort(op, op + m);
    int ans = 0, r = -1;
    for (int i = 0; i < m; i++) {
        if (op[i].l <= r && r <= op[i].r);
        else r = op[i].r, ans++;
    }
    cout << ans << endl;
    return 0;
}

区间连续和问题

        区间连续和问题:给定一个序列区间，求所有的连续子区间使得区间中的数值之和为一个确定的数。
        朴素做法是暴力枚举每一个值，向右求和，时间复杂度O(n²)。
        可以用一个数组求前缀和，得到一个前缀和p时，检查前面已求出的前缀和s=p-m的个数(m就是题目给出的求和确定值)并计入答案。这个个数在前缀和范围已知时可以用数组储存，否则需要用到STL中的map。时间复杂度O(n)。
示例代码(这里取m=47)

#include<iostream>
#include<map>

#define MAXN 1000000
using namespace std;
int op[MAXN];
long long sum[MAXN];
map<long long, int> m;

int main() {
    ios::sync_with_stdio(false);
    int ans = 0, n;
    cin >> n;
    m.clear();
    for (int i = 0; i < n; i++) {
        cin >> op[i];
        if (i == 0)sum[0] = op[0];
        else sum[i] = op[i] + sum[i - 1];
        if (m.count(sum[i] - 47) != 0)ans += m[sum[i] - 47];
        if (sum[i] == 47)ans++;
        if (m.count(sum[i]) == 0)m[sum[i]] = 1;
        else m[sum[i]]++;
    }
    cout << ans << endl;
    return 0;
}

最大区间连续和问题

        给定一串数，从中选出一段连续子区间，使得这个区间中所有数的和最大，求这个最大值。
        朴素做法是求前缀和，再在O(n²)的时间复杂度下求出所有连续和找到最大值，这里介绍一种动态规划方法。
        若令dp(x)为以序号为x的数结尾的最大连续和，那么有状态转移方程：

$dp(x)=\max\{value(x)，value(x)+dp(x-1)\}$

初始化dp(0)=value(0)。最后在所有dp值中找到最大值即可，时间复杂度O(n)。

#include<iostream>

using namespace std;
int op[500], dp[500];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)cin >> op[i];
    dp[0] = op[0];
    for (int i = 1; i < n; i++)
        if (dp[i - 1] >= 0)dp[i] = dp[i - 1] + op[i];
        else dp[i] = op[i];
    int ans = static_cast<int>(-1e8);
    for (int i = 0; i < n; i++)ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}

从上面的例子可以看出贪心与动态规划的内在联系，贪心其实是特殊情况下的动态规划。贪心利用了动态规划特殊的性质，与其说其贪，更不如说其是一种智慧。