每日一题C++版（区间合并）
编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）
特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。
区间合并
题目描述
现有一些离散的区间，对这些区间进行合并。
输入描述
输入n行，每行有两个数字，分别表示区间的最大值和最小值
输出描述
输出m行，表示合并后的区间，无法合并的区间放在下一行
示例
输入
1 3
2 4
7 8
3 5
输出
1 5
7 8
解析
对于区间合并的问题，我们首先来看[a b]和[c d]两个区间什么时候不可以合并，我们可以将两个区间想象成是两个木棒，当木棒碰不到一起的时候也就是两个区间不能合并的时候，即db的时候，也就是一个区间的下限要比另一个区间的上限要大的时候。当确定两个区间能够合并的时候，两个区间的下限就是两个下限的最小值，上限就是上限的最大值。可以用algorithm库里面的min函数和max函数来实现。
当若干个区间进行合并的时候，我们可以将其放入到一个容器内，从中取出一个区间，放入到一个新容器中，看能否和另一容器的区间进行合并，如果不可以合并，就将其存入到新容器内，知道将所有就容器内的元素都循环一遍，但是这里面存在一个问题，就是仅仅循环一次是否能实2现所有都合并的情况。显然是不可以的，我们举一个例子，旧容器中存着的是[1 4]，[5 7]，[2 6]三个区间，如果进行一次循环，得到的结果应该是[1 4]，[2 7]。但是正确的结果应该是[1 7]。因此我们需要再进行一次循环。那么我们应该循环多少次呢？当旧容器内所有元素之间都无法进行合并的时候，也就是每次取出一个区间都要原封不动的存入新的容器中的时候。即新的容器大于等于原容器的大小的时候。因此可以通过递归来实现，而递归的退出条件就是前面所说的内容。
当然，本题如果使用关联容器map可以变得简单，因为map容器里面的数是有序排放的，感兴趣的小伙伴可以自己尝试一下。
代码
include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<vector<int> > IntV;
IntV combine(IntV last);
int main()
{
int a, b;
IntV intv;
while (cin>>a>>b)
{
vector<int> med;
med.push_back(a);
med.push_back(b);
intv.push_back(med);
}
IntV last;
last = combine(intv);
for (auto m : last)
{
cout << m[0] << " " << m[1] << endl;
}
return 0;
}
IntV combine(IntV last)
{
int last_size = last.size();
IntV next;
vector<int> med;
for (int i = 0; i < last_size; i++)
{
for (int j = 1; i + j < last_size; j++)
{
if (last[i][1]<last[i+j][0]||last[i][0]>last[i+j][1])
{
med.push_back(last[i][0]);
med.push_back(last[i][1]);
next.push_back(med);
med.clear();
}
else
{
last[i + j][0] = min(last[i][0], last[i + j][0]);
last[i + j][1] = max(last[i][1], last[i + j][1]);
break;
}
}
}
next.push_back(last[last_size - 1]);
if (last_size==next.size())
{
return next;
}
else
{
IntV renext;
renext = combine(next);
return renext;
}
}
