区间覆盖(贪心)

区间覆盖

描述

给定n个闭区间[ai; bi]，其中 i=1,2,…,n。 这些区间的总和可以表示为闭合的成对非相交区间的总和。 我们要用最少的间隔找到这样的表示。 此表示的间隔应按升序写入输出。 我们说区间 [a; b] 和 [c; d] 是升序当且仅当 a <= b < c <= d。
输入一系列间隔的描述，计算满足上述条件的成对非相交区间，升序输出计算出的区间

输入描述

在输入的第一行有一个整数 n，3 <= n <= 50000。这是间隔数。 在第i+1行，1 <= i <= n，有区间[ai; bi] 形式为两个整数 ai 和 bi 由一个空格隔开，分别是区间的开始和结束，1 <= ai <= bi <= 1000000。

输出描述

输出应包含所有计算的成对非相交区间的描述。 在每一行中都应该写一个区间的描述。 它应该由两个整数组成，由一个空格隔开，分别是间隔的开始和结束。 间隔应按升序写入输出。

用例输入

5
5 6
1 4
10 10
6 9
8 10

用例输出

1 4
5 10

点击查看代码 
#include 
#include 
using namespace std;
typedef struct point
{
    int x;
    int y;

} point;//存区间
bool cmp(point q, point w)
{
    return q.x < w.x;
}
point a[50001];
int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].x >> a[i].y;
    }
    sort(a, a + n, cmp);
    int wl = a[0].x;
    int wr = a[0].y;
    for (int i = 0; i < n; i++)
    {
        if (a[i].y <= wr)
            continue;
        if (a[i].x <= wr)
        {
            wr = a[i].y;
        }
        if (a[i].x > wr)
        {
            cout << wl << " " << wr << endl;//新的区间段
            wl = a[i].x;
            wr = a[i].y;
        }
    }
    cout<

这道题和思路相似

解题记录

相关

[解题记录] P2629 好消息，坏消息

BUAA_OS_lab2上机Extra解题记录

标签