前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >秒懂力扣区间题目:重叠区间、合并区间、插入区间

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

作者头像
灵魂画师牧码
发布2020-11-06 12:48:23
7.7K0
发布2020-11-06 12:48:23
举报
文章被收录于专栏:灵魂画师牧码

今天的力扣打卡题是 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 解释: 不存在重叠区间。

思路分析

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

代码实现

代码语言:javascript
复制
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] 可被视为重叠区间。

思路分析

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

代码实现

代码语言:javascript
复制
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. 最后将新区间右边且相离的区间加入结果集。

代码实现

代码语言:javascript
复制
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 删除

本文分享自 编程如画 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、判断区间是否重叠
    • 题目描述
      • 思路分析
        • 代码实现
        • 二、合并区间
          • 题目描述
            • 思路分析
              • 代码实现
              • 三、插入区间
                • 题目描述
                  • 思路分析
                    • 代码实现
                    • 四、题目拓展
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档