区间贪心

发表于 分类于 ，

区间覆盖:

问题描述:

给定 \(n\) 个区间 \([s_i,t_i]\), 选择最少的区间， 覆盖给定区间 \([s,t]\)

思路:

将区间按 \(s_i\) 从小到大排序， 如果第一个起点 \(s_1 > s\), 则无解， 否则选取 \(t_i\) 离 \(s\) 最远的区间.

此时可将指定区间视作 \([t_i+1,t]\), 继续上述操作，直至 \(t_i \ge t\)

代码:

(poj2376) Cleaning Shifts 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// poj2376
#include <cstdio>
#include <algorithm>
using namespace std;
const int Mn(25050);
struct inter    //区间(intersection)
{
    int s,e;	//区间起点及终点
    bool operator < (const inter& rhs) const	//排序方式
    {
        return s==rhs.s ? e<rhs.e : s<rhs.s;
    }
}arr[Mn];
int main()
{
    int n,t;
    scanf("%d %d",&n,&t);
    for(int i(1);i<=n;++i)	//输入
    {
        scanf("%d %d",&arr[i].s,&arr[i].e);
        if(arr[i].s>arr[i].e)
        {
            int c = arr[i].e;
            arr[i].e = arr[i].s;
            arr[i].s = c;
        }
    }
    sort(arr+1,arr+n+1);	//排序
    int p(1),ti(1);	//当前查找起点(s), 当前遍历开始的区间编号
    int ans(0);
    while(p<=t)
    {
        int ed(p-1);	//本次查找的终点
        for(;ti<=n;++ti)
        {
            if(arr[ti].s<=p)	//如果区间起点<=p
            {
                if(arr[ti].e>ed)
                    ed = arr[ti].e;
            }
            else	break;
        }
        if(ed<p)	//如果没有找到符合条件的区间
        {
            ans = -1;
            break;
        }
        p = ed+1;
        ++ans;
    }
    printf("%d\n",ans);
    return 0;
}

区间选点:

问题描述:

给定 \(n\) 个区间 \([s_i,t_i]\), 选择最少的点， 使得每个区间都包含其中一个点.

思路:

将区间按 \(t_i\) 从小到大排序， 选择第一个区间的 \(t_1\), 排除已经包含点的区间，重复此步骤直至区间全部排除完毕.

代码:

(poj1328) Radar Installation 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// poj1328
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mn(1050);
struct inter    //同上
{
    double s,e;
    bool operator < (const inter& rhs) const	//排序方法
    {
        return e==rhs.e ? s<rhs.s : e<rhs.e;
    }
}arr[Mn];
inline double harclen(int y,int r)    //半弦长
{
    return sqrt(1ll*r*r-1ll*y*y);
}
int main()
{
    int n,d;
    int cnt(0);
    while(~scanf("%d %d",&n,&d))
    {
        if(n==0 && d==0)	break;
        printf("Case %d: ",++cnt);
        bool isans(true);	//是否有解
        for(int i(1);i<=n;++i)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            if(y>d)	isans = false;
            double tmp(harclen(y,d));
            arr[i].s = x-tmp;	//区间起点
            arr[i].e = x+tmp;	//区间终点
        }
        if(!isans)
        {
            printf("-1\n");
            continue;
        }
        sort(arr+1,arr+n+1);	//排序
        double p(arr[1].e);	//当前选点
        int ans(1);
        for(int i(2);i<=n;++i)
        {
            if(arr[i].s<=p && arr[i].e>=p)	continue;	//如果该区间包含当前选点
            else    //否则更新p
            {
                ++ans;
                p = arr[i].e;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

选择不相交区间:

题目描述:

给定 \(n\) 个区间 \([s_i,t_i]\), 选择尽量多的区间， 使得所有区间互不相交.

思路:

将区间按 \(t_i\) 从小到大排序， 选择第一个区间，排除与之相交的区间，再选择 \(t_i\) 最小的区间，直至无区间剩余.

代码:

(luogu1803) 凌乱的 yyy / 线段覆盖 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// luogu1803
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Mn(1000500);
struct sect    //同上(section)
{
    int a,b;
    bool operator <(const sect& x)    //排序方式
    { return b<x.b; }
}als[Mn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i(1);i<=n;++i)
        scanf("%d %d",&als[i].a,&als[i].b);
    sort(als+1,als+n+1);    //排序
    int ans(0),ed(0);    //答案,上次终点
    for(int i(1);i<=n;++i)
    {
        if(als[i].a>=ed)    //如果不相交
        {
            ++ans;
            ed = als[i].b;
        }
    }
    printf("%d",ans);
    return 0;
}

分组不相关区间:

题目描述:

给定 \(n\) 个区间 \([s_i,t_i]\), 将区间分成最少组， 使得每组内的区间互不相交.

思路:

先将区间按 \(s_i\) 从小到大排序， 记录每个组的 \(t_i\) 的最大值 \(aq\), 遍历每个组， 若可选则直接插入并更新 \(aq\), 否则新增一组。因为按 \(s_i\) 排序后， 前面区间能够插入的组后面区间也一定能插入， 若直接插入将导致后面的区间无法插入，则先将后面区间插入， 前面区间也一定无法插入，组数不会变少.

换言之，后面的区间比前面的区间选择更多， 前面区间随机选择不会挤占后面区间的选择.

然后考虑优化，既然可以随意选择，则不妨选择最小的 \(aq_i\). 使用优先队列维护 \(aq\) 即可使时间复杂度从 \(O(n^2)\) 降至 \(O(nlogn)\)

代码:

(poj3190) Stall Reservations 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// poj3190
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int Mn(50050);
struct inter    //同上
{
    int s,e,no;	//最后是初始编号
    bool operator < (const inter& rhs) const	//排序方式
    { return s<rhs.s; }
}arr[Mn];
struct pqn    //优先队列时使用的数据结构(priority_queue node)
{
    int n,ed;	//分组编号, 分组中t_i最大值
    bool operator > (const pqn& rhs) const	//重载大于运算
    { return ed>rhs.ed; }

};
int ansa[Mn];    //每个区间分组
int main()
{
    int n;
    scanf("%d",&n);
    for(int i(1);i<=n;++i)
    {
        scanf("%d %d",&arr[i].s,&arr[i].e);
        arr[i].no = i;
    }
    sort(arr+1,arr+n+1);	//对区间排序
    priority_queue<pqn,vector<pqn>,greater<pqn> >pq;	//小根堆
    pq.push((pqn){1,0});
    for(int i(1);i<=n;++i)
    {
        pqn x(pq.top());	//最小的aq_i
        if(x.ed<arr[i].s)	//如果可以插入
        {
            x.ed = arr[i].e;	//更新aq_i
            ansa[arr[i].no] = x.n;
            pq.pop(); pq.push(x);
        }
        else	//否则增加一组
        {
            x.ed = arr[i].e;
            ansa[arr[i].no] = pq.size()+1;
            x.n = pq.size()+1;
            pq.push(x);
        }
    }
    printf("%lu\n",pq.size());
    for(int i(1);i<=n;++i)
        printf("%d\n",ansa[i]);
    return 0;
}