区间重叠的问题：给定包含起始时间s和终止时间t(s < t) 的n个区间段，依据区间重叠情况衍生出来的一系列问题，一般以会议室的安排为外壳作为题目，给定n个会议的开始和结束时间，求相关问题，输入格式为：
n
s1 t1
s2 t2
...
sn tn
以下整理了三种常见题目：
1、最少会议室（最多重叠区间数）
求满足所有会议安排的最少会议室数量。即最多的相互重叠的区间数量。
如上图分析可知，可将所有时间点排序，初始化ans=0，遇到起始点+1，遇到终止点-1，即可得到任意区间段的区间重叠数量。
特殊情况：当同一区间点同时为起始点和终止点时（图中+0点），需将终止点标记排在起始点之前，即先-1再+1，否则会出现错误。
时间复杂度：时间主要耗费在排序2n个元素上，复杂度为O(nlogn)。
基于C++的示例代码如下：
1 #include
2 #include
3 using namespace std;
4
5 bool cmp(const pair
6 // 对于相同的区间点，使终点始终在起点之前
7 if(x.first == y.first) return x.second > y.second;
8 return x.first < y.first;
9 }
10
11 int main(){
12 int n, s, t;
13 vector
14 cin >> n;
15
16 for(int i = 0; i < n; i++){
17 cin >> s >> t;
18 vals.push_back(pair
19 vals.push_back(pair
20 }
21 sort(vals.begin(), vals.end(), cmp);
22
23 int K = 0, ans = 0;
24 for(int i = 0; i < vals.size(); i++){
25 // 遇到起点+1
26 if(vals[i].second == 0){
27 K++;
28 ans = ans > K ? ans : K;
29 }
30 // 遇到终点-1
31 else K--;
32 }
33 cout << ans << endl;
34 return 0;
35 }
2、最多数量会议安排（最多无重叠的区间数量）
在仅有一个会议室的情况下，求最多能满足的会议数量。即最多的无相互重叠的区间数量。
如上图所示，可用贪心法解决，按照会议结束时间排序，首先取第一个结束的会议，并记录结束时间end_t（图中红色点），依次遍历后续会议，若某会议的开始时间不小于end_t（图中蓝色点），则可安排该会议，同时更新end_t。
特殊情况：当结束时间相等时，开始时间的顺序其实无关紧要，如上图第三四行，两个会议均可，且安排后end_t相同，对后续安排不影响；若同时要求优先安排较长时间的会议、或者保证会议室总使用时间较长，可以在结束时间相等的情况下，使开始时间升序排列。
时间复杂度：时间主要耗费在排序n个元素上，复杂度为O(nlogn)。
基于C++的示例代码如下：
1 #include
2 #include
3 using namespace std;
4
5 bool cmp(const pair
6 // 对于结束时间相同的，按起始时间升序排列
7 if(x.second == y.second) return x.first < y.first;
8 // 按结束时间升序排列
9 return x.second < y.second;
10 }
11
12 int main(){
13 int n, s, t;
14 vector
15 cin >> n;
16
17 for(int i = 0; i < n; i++){
18 cin >> s >> t;
19 vals.push_back(pair
20 }
21 sort(vals.begin(), vals.end(), cmp);
22
23 int end_t = -1, ans = 0;
24 for(int i = 0; i < vals.size(); i++){
25 // 若当前会议开始时间不小于上一个安排会议的结束时间，则可安排
26 if(vals[i].first >= end_t){
27 ans++;
28 end_t = vals[i].second;
29 }
30 }
31 cout << ans << endl;
32 return 0;
33 }
3、最长时间会议安排（最多无重叠的区间长度）
在仅有一个会议室的情况下，求最长的能满足的会议时间。即最多无相互重叠的区间长度。
该问题用动态规划解决，首先将会议按结束时间排序，dp[i]表示以安排第i个会议作为最后一个会议时前i个会议能满足的最长时间，递推关系为dp[i] = (ti - si) + MAX{dp[j]}，其中0<=j
特殊情况：对于结束时间相等的会议，按照开始时间顺序排序。
时间复杂度：排序n个元素复杂度为O(nlogn)，动态规划复杂度为O(n2)，整体复杂度为O(n2)。
基于C++的示例代码如下：
1 #include
2 #include
3 #include
4 using namespace std;
5
6 bool cmp(const pair
7 // 对于结束时间相同的，按起始时间升序排列
8 if(x.second == y.second) return x.first < y.first;
9 // 按结束时间升序排列
10 return x.second < y.second;
11 }
12
13 int main(){
14 int n, s, t;
15 vector
16 cin >> n;
17
18 for(int i = 0; i < n; i++){
19 cin >> s >> t;
20 vals.push_back(pair
21 }
22 sort(vals.begin(), vals.end(), cmp);
23
24 vector
25 int ans = 0;
26 for(int i = 0; i < vals.size(); i++){
27 int mmax = 0;
28 for(int j = 0; j < i; j++){
29 // mmax = max{dp[j]}, for all 0 <= j < i and si >= tj
30 if((vals[i].first >= vals[j].second) && (dp[j] > mmax)){
31 mmax = dp[j];
32 }
33 }
34 // dp[i] = (ti - si) + max{dp[j]}
35 dp[i] = vals[i].second - vals[i].first + mmax;
36 ans = ans > dp[i] ? ans : dp[i];
37 }
38 cout << ans << endl;
39 return 0;
40 }