真·区间问题集 By cellur925

cellur925 · 2018-10-28 23:20:12 · 个人记录

本文总结自华东师大二附中 周小博的论文《浅谈信息学中的区间问题》 侵删.

1.最大区间调度问题：

数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。

算法：将区间们按右端点排序，顺序处理区间，记录一个当前最右端的边界值，每次与之比较/更新。

例题：Luogu P1803凌乱的yyy

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

int n,tot;
struct noip{
    int begin;
    int end;
}a[1000010];

bool cmp(noip p,noip q)
{
    return p.end<q.end;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].begin,&a[i].end);
    sort(a+1,a+n+1,cmp);
    int j=1;
    int last=a[1].end;
    int tot=1; 
    while(j<=n)
    {
        j++;
        if(a[j].begin>=last) 
        {
            tot++; 
            last=a[j].end;
        }
    }
    printf("%d",tot);
    return 0;
}

其中复杂度排序O(nlogn)，扫描O(n)。

2.最小区间覆盖问题

有n个区间，选择尽量少的区间，使得这些区间完全覆盖某线段[s,t]。

算法：将区间们按左端点排序，每次处理一个区间时找出覆盖点s的右端点最大的区间，并把它当成新的s，知道当前区间包含t。

例题：引水入城的第二步。

    sort(p+1,p+tot+1,cmp);
    int s=1;
    for (int i=1;i<=m;i++) 
    {
        int r=0;
        for (int j=1;j<=m;j++) 
            if (p[j].l<=s&&p[j].r>=s) r=max(r,p[j].r);
        ans++;
        s=r+1;
        if (s>m) break;
    }

复杂度