NC37 合并区间【牛客网】

零、原题链接

NC37 合并区间

一、题目描述

二、测试用例

三、解题思路

1. 基本思路：
     申请一个 val 大小的空间，对于一个区间，我们在区间开始位置的下标存放区间结束位置，如果对于位置已存在数字，则取二者最大值。这样在遍历区间时，如果遇到一个区间开始，则读取其结束位置，判断与当前区间结束位置谁更大，如果比当前结束位置大，则更新区间结束位置，否则不更新，直到遍历到结束位置，这样就成功合并一个区间，从到到尾遍历一篇，则所有能合并区间都合并。
2. 具体思路：
   • 申请一个 val 大小的向量，初始化为 -1 ；
   • 遍历所有区间，数组下标表示区间开始，数组内容表示区间结束；
   • 遍历数组，
     • 如果是 -1 ，则跳过；
     • 如果非 -1 ，则开始合并区间；
       • 更新遍历范围为数组值，即区间的结束
       • 遍历，如果遇到非 -1 ，则表示碰到一个可合并的区间，取其结束位置，如果比当前结束位置远，则更新结束位置
     • 合并区间结束，则将区间存放到 ans 中。
   • 返回答案 ans 。

四、参考代码

时间复杂度：$\mathrm{O}(val)$
空间复杂度：$\mathrm{O}(val)$

/*** struct Interval {*  int start;*  int end;*  Interval(int s, int e) : start(start), end(e) {}* };*/
#include <vector>
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param intervals Interval类vector* @return Interval类vector*/vector<Interval> merge(vector<Interval>& intervals) {int _max = 200001;vector<int> vec(_max, -1);vector<Interval> ans;for (int i = 0; i < intervals.size(); i++) {vec[intervals[i].start] = max(vec[intervals[i].start], intervals[i].end);}for (int i = 0; i < _max; i++) {if (vec[i] == -1)continue;Interval t;t.start = i;t.end = vec[i];while (i <= t.end) {t.end = max(t.end, vec[i]);i++;}i--;ans.emplace_back(t);}return ans;}
};