leetcode刷题12——区间系列

1.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

考察知识点：排序

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> v;
        v.push_back(intervals[0]);
        for(int i=1;i<intervals.size();++i)
        {
            int left=intervals[i][0],right=intervals[i][1];
            if(left>v.back()[1])
                v.push_back(intervals[i]);
            else
                v.back()[1]=max(right,v.back()[1]);
        }
        return v;
    }
};
           

2.插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

考察知识点：模拟

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> v;
        int left=newInterval[0],right=newInterval[1];
        bool placed=false;
        for(int i=0;i<intervals.size();++i)
        {
            if(intervals[i][1]<left)
                v.push_back(intervals[i]);
            else if(intervals[i][0]>right)
            {
                if(!placed)
                {
                    v.push_back({left,right});
                    placed=true;
                }
                v.push_back(intervals[i]);
            } 
            else
            {
                left=min(intervals[i][0],left);
                right=max(intervals[i][1],right);                        
            }
        }
        if(!placed)
            v.push_back({left,right});
        return v;
    }
};
           

3.汇总区间

给定一个无重复元素的有序整数数组 nums 。返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

“a->b” ，如果 a != b

“a” ，如果 a == b

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int n=nums.size();
        if(n==0)  return {};
        vector<string> v;
        string s;
        int left=0,right=0;
        for(int i=1;i<n;++i)
        {
            if(long(nums[i])-long(nums[i-1])>1)
            {
                right=i-1;
                if(left==right)
                    s=to_string(nums[left]);
                else
                    s=to_string(nums[left])+"->"+to_string(nums[right]);
                v.push_back(s);
                left=i;
            }
        }
        if(left==n-1)
             s=to_string(nums[left]);
        else
             s=to_string(nums[left])+"->"+to_string(nums[n-1]);
         v.push_back(s);
        return v;
    }
};