区间重合--c++

╰半夏微凉° 2023-06-20 15:55 16阅读 0赞

# 题目简述 #

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

**示例 1:**

输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

**示例 2:**

输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

## 解题思路 ##

1.  先排序（按照区间的第一位置的数值大小排序，从小到大），这里采用快速排序
2.  记录当前的区间（用内存来记录目前记录的区间，不断迭代这个区间直到完成目标之后，再存起来）

## 代码 ##

class Solution { 
    public:
        void sort (vector<vector<int>> &a,int s,int e){ 
            if (s >= e)
                return;
            int i = s, j = e;
            vector<int> k = a[s];
            while (i < j) { 
                while ( i < j && a[j][0] >= k[0])
                    --j;
                if ( i < j ) { 
                    a[i] = a[j];
                }
                while ( i < j && a[i][0] <= k[0])
                    ++i;
                if ( i < j ) { 
                    a[j] = a[i];
                }
            }
            a[i] = k;
            sort(a,s,i-1);
            sort(a,i+1,e);
        }
        vector<vector<int>> merge(vector<vector<int>>& intervals) { 
            int i, j, last=-1;
            vector<vector<int>> ans;
            sort(intervals, 0, intervals.size() -1);
            for (int index=0; index<intervals.size(); ++index) { 
                if (last == -1 || intervals[index][0] > j){ 
                    if (last != -1){  // end
                        ans.push_back(vector<int>({ i, j}));
                    }
                    i = intervals[index][0];
                    j = intervals[index][1];
                    last = index;
                } else { 
                    i = i < intervals[index][0]? i:intervals[index][0];
                    j = j > intervals[index][1]? j:intervals[index][1];
                }
            }
            if (last != -1){  // end
                ans.push_back(vector<int>({ i, j}));
            }
    
            return ans;
        }
    };