区间合并

给定 n个区间 [l_i,r_i]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3]和 [2,6] 可以合并为一个区间 [1,6]。

思路

按左端点排序，再维护一个区间，与后面一个个区间进行三种情况的比较，存储到数组里去。

代码实现

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

using namespace std;
typedef pair<int,int> PII;
int n;

void merge(vector<PII> &segs)
{
  vector<PII> res;
  sort(segs.begin(), segs.end());
  
  int st = -2e9, ed = -2e9;
  for(auto seg: segs)
  {
    if( seg.first > ed )
    {
      st = seg.first, ed = seg.second;
      if( st != -2e9 )res.push_back({st, ed});
    }
    else{
      ed = max(ed, seg.second);
    }
  }
  
  segs = res;
}

int main()
{
  cin >> n;
  vector<PII> segs;
  while( n -- )
  {
    int l, r;
    cin >> l >> r;
    segs.push_back({l, r});
  }
  
  merge(segs);
  
  
  cout << segs.size() << endl;
  return 0;
}