专栏首页灵魂画师牧码秒懂力扣区间题目:重叠区间、合并区间、插入区间

秒懂力扣区间题目:重叠区间、合并区间、插入区间

今天的力扣打卡题是 57. 插入区间 ,我们再顺便练习两道类似的简单区间题目,比如:判断区间是否重叠(252. 会议室)56. 合并区间。这类面试题目还挺讨巧的,因为不需要掌握什么数据结构与算法的先验知识,看懂题目之后模拟一遍即可,很容易考察出应聘者到底会不会写代码。

一、判断区间是否重叠

题目描述

力扣 252. 会议室 难度:Easy 给定一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,请你判断一个人是否能够参加这里面的全部会议。 8 示例 1:: 输入: intervals = [[0,30],[5,10],[15,20]] 输出: false 解释: 存在重叠区间,一个人在同一时刻只能参加一个会议。 示例 2:: 输入: intervals = [[7,10],[2,4]] 输出: true 解释: 不存在重叠区间。

思路分析

因为一个人在同一时刻只能参加一个会议,因此题目实质是判断是否存在重叠区间,这个简单,将区间按照会议开始时间进行排序,然后遍历一遍判断即可。

代码实现

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // 将区间按照会议开始实现升序排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历会议,如果下一个会议在前一个会议结束之前就开始了,返回 false。
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

二、合并区间

题目描述

力扣 56. 合并区间 难度:Medium 给出一个区间的集合,请合并所有重叠的区间。 示例 1:: 输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。 示例 2:: 输入: intervals = [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路分析

和上一题一样,首先对区间按照起始端点进行升序排序,然后逐个判断当前区间是否与前一个区间重叠,如果不重叠的话将当前区间直接加入结果集,反之如果重叠的话,就将当前区间与前一个区间进行合并。

代码实现

class Solution {
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的,或者当前区间的起始位置 > 结果数组中最后区间的终止位置,说明不重叠。
            // 则不合并,直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之说明重叠,则将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}

三、插入区间

题目描述

57. 插入区间 难度:Medium 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然 有序且不重叠(如果有必要的话,可以 合并区间)。 示例 1:: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 解释: 新区间[2,5] 与 [1,3]重叠,因此合并成为 [1,5]。 示例 2:: 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 新区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠,因此合并成为 [3,10]。

思路分析

本题中的区间已经按照起始端点升序排列,因此我们直接遍历区间列表,寻找新区间的插入位置即可。具体步骤如下:

  1. 首先将新区间左边且相离的区间加入结果集(遍历时,如果当前区间的结束位置小于新区间的开始位置,说明当前区间在新区间的左边且相离);
  2. 接着判断当前区间是否与新区间重叠,重叠的话就进行合并,直到遍历到当前区间在新区间的右边且相离,将最终合并后的新区间加入结果集;
  3. 最后将新区间右边且相离的区间加入结果集。

代码实现

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
        // 遍历区间列表:
        // 首先将新区间左边且相离的区间加入结果集
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res[idx++] = intervals[i++];
        }
        // 接着判断当前区间是否与新区间重叠,重叠的话就进行合并,直到遍历到当前区间在新区间的右边且相离,
        // 将最终合并后的新区间加入结果集
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res[idx++] = newInterval;
        // 最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
            res[idx++] = intervals[i++];
        }

        return Arrays.copyOf(res, idx);
    }
}

四、题目拓展

力扣1288. 删除被覆盖区间 难度:Easy

给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。在完成所有删除操作后,请你返回列表中剩余区间的数目。(对于区间 [a,b) 和区间 [c,d),若 c <= ad >= b ,则区间 [a,b) 被区间 [c,d) 覆盖)

示例输入:intervals = [[1,4],[3,6],[2,8]] 输出:2 解释:区间 [3,6] 被区间 [2,8] 覆盖,所以它被删除了。

思路分析:本题和本文第一题的做法一样~首先按照区间起始端点进行排序,然后遍历区间,将第一题的判断区间是否重叠改为判断区间是否覆盖即可。

力扣228. 汇总区间 难度:Medium

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

示例输入:nums = [0,1,2,4,5,7] 输出:["0->2","4->5","7"]

思路分析:本题是在有序数组中,找出连续递增的区间,是双指针/滑动窗口的经典题目,和本文中的其他区间题目不是一种类型,我们在之后的文章中再介绍双指针和滑动窗口的模板哈~

力扣354. 俄罗斯套娃信封问题 难度:Hard

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

示例输入:envelopes = [[5,4],[6,4],[6,7],[2,3]] 解释:最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

思路分析:本题实质是求最长嵌套区间的长度,是经典题目「最长上升子序列」的变种,解法也一模一样,有动态规划

O(N^2)

和 二分

O(NlogN)

两种经典解法。由于本题和本文中的其他区间题目不是一种类型,所以我们在后续的章节里再「秒懂最长上升子序列问题及其系列变种」吧!

来个直击灵魂的三连吧!

文章分享自微信公众号:
编程如画

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

原始发表时间:2020-11-05
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 【python-leetcode57-区间合并】插入区间

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

    西西嘛呦
  • 【题目】合并区间

    https://leetcode-cn.com/problems/merge-intervals/

    谙忆
  • LintCode 合并区间题目代码

    desperate633
  • LintCode 插入区间题目分析代码

    给出一个无重叠的按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你要确保列表中的区间仍然有序且不重叠 (如果有必要的话,可以合并区间)。

    desperate633
  • 关于leetcode第56题合并重复区间的解析

    https://leetcode-cn.com/problems/merge-intervals/

    冬天里的懒猫
  • LeetCode 57. 插入区间(一次遍历)

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

    Michael阿明
  • LeetCode 57. 插入区间

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

    韩旭051
  • LeetCode 56. 合并区间(优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/merge-intervals 著作权归领扣网络所有...

    Michael阿明
  • LeetCode 435. 无重叠区间(贪心/动态规划)

    注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

    Michael阿明

扫码关注腾讯云开发者

领取腾讯云代金券