贪心区间问题

区间选点

给定N个闭区间[ai, bi]，选择尽量少的点使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量
时间复杂度O(nlogn)

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
#include <iostream>
#include <algorithm>

#define fi first
#define se second
typedef pair<int, int> PII;

const int N = 100010;

int n;
PII a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        a[i] = {r, l};
    }

    //按右端点排序 pos选右端点
    sort(a, a + n);

    int res = 1, pos = a[0].fi;
    for (int i = 0; i < n; i ++ )
    {
        //当前选的点能穿过当前区间
        if (a[i].se <= pos && a[i].fi >= pos) continue;
        res ++ ;
        pos = a[i].fi;
    }

    cout << res;

    return 0;
}

区间合并

n个闭区间[li, ri]合并所有有交集的区间，输出合并后的区间个数
时间复杂度O(nlogn)

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
#include <iostream>
#include <algorithm>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        a[i] = {l, r};
    }

    //左端点排序
    sort(a, a + n);

    int res = 1, r = a[0].se;
    for (int i = 1; i < n; i ++ )
    {
        if (r < a[i].fi)  //无交集
        {
            res ++ ;
            r = a[i].se;
        }
        else r = max(r, a[i].se);
    }
    cout << res;

    return 0;
}

区间分组

N个闭区间[ai, bi]，将这些区间分组，每组内部的区间两两之间(包括端点)没有交集
求出最小组数
时间复杂度O(nlogn)

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
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII a[N];
priority_queue<int, vector<int>, greater<int>> h;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        a[i] = {l, r};
    }

    sort(a, a + n);

    h.push(a[0].se);
    for (int i = 1; i < n; i ++ )
    {
        int l = a[i].fi, r = a[i].se;
        if (l <= h.top()) h.push(r);  //无处放，加新组
        else   //更新h中最小的r
        {
            h.pop();
            h.push(r);
        }
    }
    cout << h.size();

    return 0;
}

最大不相交区间数量

N个闭区间[ai,bi]，选若干区间，使得选中的区间之间互不相交
输出可选区区间的最大数量
时间复杂度O(nlogn)

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
#include <iostream>
#include <algorithm>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        a[i] = {r, l};
    }

    //按右端点排序 pos选右端点
    sort(a, a + n);

    int res = 1, pos = a[0].fi;
    for (int i = 0; i < n; i ++ )
    {
        if (a[i].se <= pos && a[i].fi >= pos) continue;
        res ++ ;
        pos = a[i].fi;
    }

    cout << res;

    return 0;
}

区间覆盖

N个闭区间[ai,bi]以及一个线段区间[bg,en]，选择尽量少的区间将该线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖输出-1.
时间复杂度O(nlogn)

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
#include <iostream>
#include <algorithm>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int bg, en, n;
PII a[N];
bool success;

int main()
{
    cin >> bg >> en >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        a[i] = {l, r};
    }

    sort(a, a + n);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int mxr = -2e9, j = i;
        while (j < n && a[j].fi <= bg)
        {
            mxr = max(mxr, a[j].se);
            j ++ ;
        }

        res ++ ;

        if (mxr < bg) break;

        if (mxr >= en)
        {
            success = true;
            break;
        }

        bg = mxr;
        i = j - 1;
    }
    if (success) cout << res;
    else puts("-1");

    return 0;
}