区间合并c++-创新互联

今天给大家讲解一下区间合并的题目；

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

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

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

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

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

然后我给大家讲解一下代码；讲解放在代码里；

#include
#include
#include

using namespace std;

typedef pairPII;

void merge(vector&segs)
{
  vectorres;
  sort(segs.begin(), segs.end());//排序；
  int st = -2e9, ed = -2e9;//设定边界；
  for (auto seg : segs)//进行遍历，C++11的特性；
  if (ed< seg.first)
  {
  if (st != -2e9) res.push_back({st, ed});
  st = seg.first, ed = seg.second;
  }
  else ed = max(ed, seg.second);
  if (st != -2e9) res.push_back({st, ed});
  segs = res;
}

int main()
{
  int n;
  scanf("%d", &n);
  vectorsegs;
  for (int i = 0; i< n; i ++ )
  {
  int l, r;
  scanf("%d%d", &l, &r);
  segs.push_back({l, r});
  }
  merge(segs);
  cout<< segs.size()<< endl;
  return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧