Problem Description

给你若干个闭区间,请你合并所有重叠的区间。

Input

输入若干行,每行两个整数表示某个闭区间的左右端点值。端点的数值都在正整数范围内。

Output

输出若干行,每行为一个合并后的闭区间的左右端点值。这些区间的按左端点排序。

Sample Input

1 3
2 6
8 10
15 18
\0

Sample Output

1 6
8 10
15 18

代码:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Range
{
public:
    int A, B;
    Range(int _A, int _B)
    {
        A = _A;
        B = _B;
    }
};

int main(int argc, char const *argv[])
{
    vector<Range> ranges;

    int a, b;

    while (cin >> a >> b)
    {
        ranges.push_back(Range(a, b));
    }

    sort(ranges.begin(), ranges.end(), [](Range a, Range b) { return a.A < b.A; });

    for (int i = 0; i < ranges.size() - 1; i++)
    {
        if (ranges[i + 1].A > ranges[i].B)
        {
            continue;
        }
        else
        {
            ranges[i + 1].A = min(ranges[i].A, ranges[i + 1].A);
            ranges[i + 1].B = max(ranges[i].B, ranges[i + 1].B);

            ranges[i].A = -1;
        }
    }

    for (auto i = ranges.begin(); i != ranges.end(); ++i)
    {
        if (i->A == -1)
        {
            continue;
        }

        cout << i->A << " " << i->B << endl;
    }

    return 0;
}
分类: 未分类

发表评论

电子邮件地址不会被公开。