区间合并

区间合并（模板）

题目

给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。

输入格式

第一行为一个整数n，3 ≤ n ≤ 50000。表示输入区间的数量。
之后n行，在第i行上（1 ≤ i ≤ n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 [ai; bi]（其中 1 ≤ ai ≤ bi ≤ 10000）。

输入格式

输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。

输入样例1

5
5 6
1 5
10 10
6 9
8 10

输出样例1

1 10

题解

首先按左边元素最小进行排序，若相同则按照右边元素最小排序。
注意合并区间的边界问题

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6;
int _;

vector<pair<int, int>> a;
int n;

int cmp(const pair<int, int> &x, const pair<int, int> &y) {
    if(x.fi == y.fi) {
        return x.se < y.se;   //左相同，则按右最小排列
    } 
    return x.fi < y.fi;  //按照左最下排列
}

void solve() {
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].fi >> a[i].se;
    }  
    sort(a.begin(), a.end(), cmp);
    int l = a[0].fi, r = a[0].se;
    for(int i = 1; i < n; i++) {
        if(a[i].fi > r) {
            cout << "no\n";
            return;
        }
        l = min(l, a[i].fi);
        r = max(r, a[i].se);
    }
    cout << l << " " << r << "\n";
}   
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    _ = 1;
    // cin >> _;
    while(_--) {
        solve();
    }
    return 0;
}

管道（区间合并例题）

题目

有一根长度为 len的横向的管道，该管道按照单位长度分为 len段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

\[一开始管道是空的，位于 L_i的阀门会在 S_i时刻打开，并不断让水流入管道。 \]

\[对于位于 L_i的阀门，它流入的水在 T_i（T_i ≥ S_i）时刻会使得从第 L_i−(T_i−S_i)段到第 L_i+(T_i−S_i)段的传感器检测到水流。 \]

求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 n, len，用一个空格分隔，分别表示会打开的阀门数和管道长度。

\[接下来 n行每行包含两个整数 L_i,S_i，用一个空格分隔，表示位于第 Li段管道中央的阀门会在 S_i时刻打开。 \]

输出格式

输出一行包含一个整数表示答案。

数据范围

\[对于 30%的评测用例，n ≤ 200，S_i, len≤3000； \]

\[对于 70%的评测用例，n ≤ 5000，S_i,len≤105； \]

\[对于所有评测用例，1 ≤ n ≤ 10^5，1 ≤ S_i, len ≤ 10^9，1 ≤ L_i ≤ len，L_{i-1} < L_i。 \]

样例

输入样例1

输出样例1

题解

首先理解题意，把阀门取L点，而不是区间，只看点，所以\(L_i\)点在\(S_i\)时刻开始检测水流，一直向两边扩展, 而我们现在求的是最早时间覆盖整个管道，一共L个阀门，也就是L个区间。

该题目需要用到二分+区间合并

该题目的区间合并需要注意的点是，两个点只要相邻即可合并，而不需要[1, 4], [4, 5]，而是[1, 2], [3, 5]

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6;
int _;

vector<pair<ll, ll>> a;
ll b[N][2];
int n, len;
ll ans;

int cmp(const pair<ll, ll> &x, const pair<ll, ll> &y) {
    if(x.fi == y.fi) {
        return x.se < y.se;
    } 
    return x.fi < y.fi;
}

bool check(ll x) {          // 区间合并，主要判断当前的时间能否覆盖整个管道
    a.clear();
    for(int i = 0; i < n; i++) {
        ll l = 0, r = 0;
        if(x >= b[i][1]) {
            l = b[i][0] - (x - b[i][1]);
            l = max((ll)1, l);
            r = b[i][0] + (x - b[i][1]);
            r = min((ll)len, r);
            a.push_back(make_pair(l, r));
        }
    }
    
    sort(a.begin(), a.end(), cmp);
   
    ll l = a[0].fi, r = a[0].se;
    for(int i = 1; i < SZ(a); i++) {
        if(a[i].fi - 1 > r) {
            return 0;
        }
        l = min(l, a[i].fi);
        r = max(r, a[i].se);
    }
    // cout << "l, r = ";
    // cout << l << " " << r << '\n';
    if(l == 1 && r == len) return true;
    return false;
}

void solve() {
    cin >> n >> len;
    for(int i = 0; i < n; i++) {
        cin >> b[i][0] >> b[i][1];
    }
    ll l = 1, r = 2*1e9;
    while(l <= r) {                // 二分一个时间点，注意设置区间初始值大小
        ll mid = (l + r) / 2;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
}   
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    _ = 1;
    // cin >> _;
    while(_--) {
        solve();
    }
    return 0;
}