题解 | #合并区间# 桶排序

描述

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0≤𝑛≤2×10⁵，区间内 的值都满足 0≤𝑣𝑎𝑙≤2×10⁵

解法

采用桶排序，时间复杂度𝑂(𝑣𝑎𝑙)，空间复杂度𝑂(𝑣𝑎𝑙)

static const auto io_sync_off = []()
{
    std::ios::sync_with_stdio(false);//关闭输入输出
    std::cin.tie(nullptr);//取消两个stream绑定
    std::cout.tie(nullptr);//取消cin 和 cout之间的绑定,加快执行效率
    return nullptr;
}();


/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
public:
    const static int N = 2e5 + 99;
    // 桶排序的“桶”
    vector<int> sortedByStart[N];

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类vector
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        // 结果
        vector<Interval> ans;

        for (auto& interval : intervals) {
            // 按照interval.start进行桶排序
            sortedByStart[interval.start].emplace_back(interval.end);
        }

        // 当前处理的Interval
        Interval* curStarted = nullptr;

        for (int i = 0;i < N;++i) {
            if (sortedByStart[i].empty()) {
                continue;
            }


            int maxEnd = *std::max_element(sortedByStart[i].begin(), sortedByStart[i].end());

            if (curStarted != nullptr && curStarted->end < i) {
                // 此区间合并结束
                ans.push_back(*curStarted);
                delete curStarted;
                curStarted = nullptr;
            }


            if (curStarted != nullptr) {
                // 若有已开始的Interval，对其end进行更新
                curStarted->end = max(maxEnd, curStarted->end);
            }
            else {
                // 无已开始的Interval，创建新的
                curStarted = new Interval(i, maxEnd);
            }
        }

        // 防止遗漏
        if (curStarted != nullptr) {
            ans.push_back(*curStarted);
            delete curStarted;
            curStarted = nullptr;
        }

        return ans;
    }
};