区间问题

这是一篇关于区间问题的算法学习文章。文章介绍了五类最常见的区间问题，并提供了相应的解决思路。

简介

区间问题大多都是用贪心来做的。

一般都是先按照区间排序，可能按照左端点或右端点从大到小或从小到大排序，然后使用贪心。

根据问题的不同，具体贪心的思路也各不相同。

这篇文章汇总了最常见的5类区间问题，并直接给出思路方便理解和记忆。

• 区间合并问题
• 选择不相交区间问题
• 区间选点问题
• 区间覆盖问题
• 区间分组问题

贪心的正确性是显然的，很容易感性理解，本文不对其进行证明。

区间合并问题

题意

给出一堆区间，要求合并所有有交集的区间 （端点处相交也算有交集）。最后问合并之后的区间个数或其它相关数据。

做法

按左端点从小到大排序，然后能与上一个区间合并就合并，不能合并就新建一个区间继续合并。

例题

P2082

struct sgm {
    int l, r;
} a[maxN + 5];
int n, res;
bool cmp(sgm x, sgm y) { return x.l < y.l; }
signed main() {
    ios;
    cin >> n;
    rep(i, 0, n - 1) { cin >> a[i].l >> a[i].r; }
    sort(a, a + n, cmp);
    sgm tmp = a[0];
    rep(i, 1, n - 1) {
        if (a[i].l <= tmp.r) {
            tmp.r = max(tmp.r, a[i].r);
        } else {
            res += tmp.r - tmp.l + 1;
            tmp = a[i];
        }
    }
    res += tmp.r - tmp.l + 1;
    cout << res;
    return 0;
}

P2434

struct sgm {
    int l, r;
} a[maxN + 5];
int n;
bool cmp(sgm x, sgm y) { return x.l < y.l; }
int main() {
    ios;
    cin >> n;
    rep(i, 0, n - 1) { cin >> a[i].l >> a[i].r; }
    sort(a, a + n, cmp);
    sgm tmp = a[0];
    rep(i, 1, n - 1) {
        if (a[i].l <= tmp.r) {
            tmp.r = max(tmp.r, a[i].r);
        } else {
            cout << tmp.l << " " << tmp.r << endl;
            tmp = a[i];
        }
    }
    cout << tmp.l << " " << tmp.r << endl;
    return 0;
}

选择不相交区间问题

题意

给出一堆区间，要求选择尽量多的区间，使得这些区间互不相交，求可选取的区间的最大数量。这里端点相同也算有重复。

做法

按右端点从小到大排序，然后依次遍历，如果遇到和前面没有重合的区间就选进去，否则就跳过。

例题

P1803

struct sgm {
    int l, r;
} a[maxN + 5];
int n, res = 1;
bool cmp(sgm x, sgm y) { return x.r < y.r; }
int main() {
    ios;
    cin >> n;
    rep(i, 0, n - 1) cin >> a[i].l >> a[i].r;
    sort(a, a + n, cmp);
    sgm tmp = a[0];
    rep(i, 1, n - 1) {
        if (a[i].l >= tmp.r) {
            res++;
            tmp = a[i];
        }
    }
    cout << res;
    return 0;
}

CF1841D

这题不是纯板题但也接近板子题，博客里有题解。

区间选点问题

题意

给出一堆区间，取尽量少的点，使得每个区间内至少有一个点（不同区间内含的点可以是同一个，位于区间端点上的点也算作区间内）。

做法

按右端点从小到大排序，因为重叠部分都是在靠右的部分，每次如果区间内没有点就把点取在区间最右端即可。

例题

CF45D

不是纯板子题

int n, ans[110];
bool fl[maxN + 5];
struct sgm {
    int l, r, id;
} a[110];
bool cmp(sgm x, sgm y) {
    if (x.r != y.r)
        return x.r < y.r;
    return x.l < y.l;
}
int main() {
    ios;
    cin >> n;
    rep(i, 1, n) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    rep(i, 1, n) {
        rep(j, a[i].l, a[i].r) {
            if (!fl[j]) {
                fl[j] = 1, ans[a[i].id] = j;
                break;
            }
        }
    }
    rep(i, 1, n) cout << ans[i] << " ";
    return 0;
}

P1250

加强版板子题（区间中的点数有最少要求）

struct sgm {
    int l, r, t;
} a[maxH + 5];
int n, h, res, fa[maxN + 5];
bool fl[maxN + 5];
int find(int x) { return x == fa[x] ? x : find(fa[x]); }
bool cmp(sgm x, sgm y) {
    if (x.r != y.r)
        return x.r < y.r;
    return x.l < y.l;
}
int main() {
    ios;
    cin >> n >> h;
    rep(i, 0, h - 1) cin >> a[i].l >> a[i].r >> a[i].t;
    sort(a, a + h, cmp);
    rep(i, 0, h - 1) {
        int cnt = 0;
        rep(j, a[i].l, a[i].r) cnt += fl[j];
        if (cnt < a[i].t) {
            int p = a[i].r;
            while (cnt < a[i].t) {
                if (!fl[p])
                    fl[p] = 1, cnt++;
                p--;
            }
        }
    }
    rep(i, 1, n) res += fl[i];
    cout << res;
    return 0;
}

区间覆盖问题

题意

给出一堆区间和一个目标区间，问最少选择多少区间可以覆盖掉题中给出的这段目标区间。

做法

按左端点从小到大排序，每次在可以覆盖到目标区间的所有线段中选择右端点最大的线段，然后将目标线段的左端点设为其右端点+1。左端点排序保证可以覆盖到目标区间的线段是连续的，因此做到复杂度 $O(n)$。

例题

U248682

int s, t, n, res;
struct sgm {
    int l, r;
} a[maxN + 5];
bool cmp(sgm x, sgm y) { return x.l < y.l; }
int main() {
    ios;
    cin >> s >> t >> n;
    rep(i, 0, n - 1) { cin >> a[i].l >> a[i].r; }
    sort(a, a + n, cmp);
    bool fl = 0;
    rep(i, 0, n - 1) {
        int j = i, maxR = -INF;
        while (j < n && a[j].l <= s) {
            maxR = max(maxR, a[j].r);
            j++;
        }
        if (maxR <= s) {
            break;
        }
        s = maxR, res++;
        if (s >= t) {
            fl = 1;
            break;
        }

        i = j - 1;
    }
    if (fl)
        cout << res << endl;
    else
        cout << "-1\n";
    return 0;
}

区间分组问题

题意

给出一堆区间，问最少可以将这些区间分成多少组，使得每个组内的区间互不相交。

做法

按左端点从小到大排序，建立一个以右端点大小为关键字的小根堆，每次判断新线段能不能和堆顶线段合并，如果可以就合并，如果不行就放入堆中，最后堆中剩下的元素个数即为最少组数。

例题

U248679

int n;
struct sgm {
    int l, r;
} a[maxN + 5];
bool operator<(sgm x, sgm y) { return x.r > y.r; }
bool cmp(sgm x, sgm y) { return x.l < y.l; }
priority_queue<sgm> q;
int main() {
    ios;
    cin >> n;
    rep(i, 0, n - 1) cin >> a[i].l >> a[i].r;
    sort(a, a + n, cmp);
    q.push(a[0]);
    rep(i, 1, n - 1) {
        if (a[i].l > q.top().r) {
            sgm tmp = q.top();
            q.pop();
            tmp.r = a[i].r;
            q.push(tmp);
        } else
            q.push(a[i]);
    }
    cout << q.size();
    return 0;
}