区间的合并与拆分

18 Aug 2024 in Algorithm Pageviews

solve actually problem!

我们从一个典型问题入手，看下区间合并问题的思考方式。

举例1

给定n个区间[l_i, r_j]，要求合并所有有交集的区间，端点处相交也需要合并，输出合并完成后区间的个数。

输入格式：

第一行整数 n。

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

输出格式：

表示合并完成后区间的个数

输入样例：

5

1 2

2 4

5 6

7 8

7 9

输出样例：

3

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> left;
    vector<int> right;
    for (int i = 0; i < n; i++) {
        int l = 0;
        int r = 0;
        cin >> l >> r;
        left.emplace_back(l);
        right.emplace_back(r);
    }
    
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());
    vector<vector<int>> res;
    for (int i = 0, j = 0; i < n; i++) {
        if ((i == n - 1) || left[i + 1] > right[i]) {
            res.push_back({left[i], right[i]});
        }
        j = i + 1;
    }
    return res.size();
}

举例2

给定一组区间，将区间进行合并，然后把合并后的区间再按照sectorSize的大小从n (n = 0)开始，按照[sectorSize * n, sectorSize * (n + 1) - 1], n 表示从第几个区间开始。

输入：

32

[[0, 30], [10, 33], [130, 150], [151, 158], [60, 100], [130, 150], [20, 50]]

输出：

[[0, 31], [32, 50], [60, 63], [64, 95], [96, 100], [130, 158]]

class Solution {
public:
    vector<pair<int, int>> IoMerge(const vector<pair<int, int>> &arr)
    {
        vector<pair<int, int>> array(arr);
        sort(array.begin(), array.end());
        vector<pair<int, int>> res;
        while (!array.empty()) {
            if (array.size() == 1) {
                res.push_back(array[0]);
                break;
            }
            
            if (array[0].second < array[1].first - 1) {
                res.push_back(array[0]);
                array.erase(array.begin());
            } else if (array[0].second < array[1].second) {
                pair<int, int> p(array[0].first, array[1].second);
                array.erase(array.begin());
                array.erase(array.begin());
                array.emplace(array.begin(), p);
            } else {
                array.erase(array.begin() + 1);
            }
        }
        return res;
    }
    
    vector<pair<int, int>> SplitArray(int n, const vector<pair<int, int>> &array)
    {
        vector<pair<int, int>> res;
        for (const auto &[left, right] : array) {
            int start = (left / n + 1) * n;
            int end = right / n * n;
            if (start > end) {
            	res.emplace_back(left, right);
                continue;
            }
            
            long long border = left;
            for (long long i = start; i <= end; i += n) {
                res.emplace_back(border, i - 1);
                border = i;
            }
            
            if (border <= right) {
                res.emplace_back(border, right);
            }
        }
        return res;
    }
};