区间合并问题

发表于 更新于 分类于 ，
本文字数： 686

区间合并问题思路

已知若干闭区间，将其中存在重复的区间合并的方法（一个区间右端点与另一个区间的左端点重合也视为重复） 例：[2,4]、[4,7]、[7,10]、[8,9]、[8,15]、[17,21]进行区间合并 结果应为[2,15]、[17,21]两个区间 我们可以将所有区间按照左端点进行排序（从小到大） 之后从第一个区间开始维护 第二个区间与第一个区间有如下几种关系：//称区间左端点为st 右端点为ed

  • st1<st2<ed2<ed1
  • st1<st2<ed1<ed2
  • st1<ed1=st2<ed2
  • st1<ed1<st2<ed2

在遍历区间时，前三种情况只需要不断更新维护区间的ed 第四种情况我们需要将当前维护的区间放入记录容器中，更新维护区间的st，ed为新的st与ed c++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<PII> a;

int merge(vector<PII> a)
{
    vector<PII> res;
    int st = a[0].first, ed = a[0].second;
    for (auto item : a)
    {
        if (ed < item.first)
        {
            res.push_back({st, ed});
            st = item.first;
        }
        ed = max(ed, item.second);
    }
    res.push_back({st, ed});
    return res.size();
}