57. Insert Interval

旧城等待， 2021-10-18 10:50 219阅读 0赞

#### description: ####

插入新的区间，涉及到区间的合并.  
**Note:**

**Example:**

Example 1:
    
    Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
    Output: [[1,5],[6,9]]
    
    Example 2:
    
    Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    Output: [[1,2],[3,10],[12,16]]
    Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

#### answer: ####

class Solution {
    public:
        vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
            int n = intervals.size(), cur = 0;
            vector<vector<int>> res;
            while (cur < n && intervals[cur][1] < newInterval[0]) {
                res.push_back(intervals[cur++]);
            }
            while (cur < n && intervals[cur][0] <= newInterval[1]) {
                newInterval[0] = min(newInterval[0], intervals[cur][0]);
                newInterval[1] = max(newInterval[1], intervals[cur][1]);
                ++cur;
            }
            res.push_back(newInterval);
            while (cur < n) {
                res.push_back(intervals[cur++]);
            }
            return res;
        }
    };

#### relative point get√： ####

#### hint : ####

第一个循环把不和给定新区间重叠的，应该放在新区间前面的区间先放在答案里  
第二个循环处理有重叠的部分，一直到后边最后一个没有重叠了退出  
最后一个循环将新区间后边的没有重叠的放到答案里

转载于:https://www.cnblogs.com/forPrometheus-jun/p/11285743.html

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode】24. 57_Insert Interval · 插入区间

题目描述英文版描述 You are given an array of non-overlapping intervals intervals where int

Dear 丶/ 2024年04月01日 11:51/ 0 赞/ 60 阅读

相关 LeetCode 57. Insert Interval和 218. The Skyline Problem

[LeetCode 57. Insert Interval][] 1. 学习了[力扣中国官方给出的思路][Link 1]。有：如果两个线段之间没有交集，其充要条件为r1

港控/mmm°/ 2023年10月04日 12:04/ 0 赞/ 24 阅读

相关 57 Insert Interval

有些hard在于算法难，思路难想；有些hard在于corner case多，这题就是后者。这题跟56. Merge Intervals是类似的，而且这个是已经排好了顺序给你

亦凉/ 2022年10月01日 07:55/ 0 赞/ 181 阅读

相关 LeetCode57——Insert Interval

LeetCode57——Insert Interval 跟上一题[LeetCode56——Merge Interval][LeetCode56_Merge Interval]

电玩女神/ 2022年08月09日 12:56/ 0 赞/ 131 阅读

相关 lkeetcode 57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merg

红太狼/ 2022年07月25日 19:59/ 0 赞/ 168 阅读

相关 [Leetcode] 57. Insert Interval

57. Insert Interval Given a set of non-overlapping intervals, insert a new interval in

怼烎@/ 2022年06月13日 03:25/ 0 赞/ 138 阅读

相关 leetcode 57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merg

痛定思痛。/ 2022年06月09日 10:54/ 0 赞/ 151 阅读

相关 LeetCode 57.Insert Interval (插入区间)

题目描述：给出一个无重叠的，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。示例

矫情吗；*/ 2022年05月10日 03:56/ 0 赞/ 176 阅读

相关【Leetcode】57. Insert Interval（模拟）

Given a set of non-overlapping intervals, insert a new interval into the intervals (merg

野性酷女/ 2022年02月28日 03:54/ 0 赞/ 155 阅读

相关 57. Insert Interval

description: 插入新的区间，涉及到区间的合并. Note: Example: Example 1: Input: inter

旧城等待，/ 2021年10月18日 10:50/ 0 赞/ 220 阅读