352. 将数据流变为多个不相交区间

题目描述 给定一个非负整数的数据流输入 a1,a2,…,an,…,将到目前为止看到的数字总结为不相交的区间列表。 例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为: [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7] 进阶:如果有很多合并,并且与数据流的大小相比,不相交区间的数量很小,该怎么办? 提示:特别感谢 @yunhong 提供了本问题和其测试用例。 https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/ 解法1 这道题我们使用TreeMap来解决。TreeMap的底层实现是R-B Tree,它的平衡性很好,对于get、put、remove、contains等操作都能够达到O(logn)的时间复杂度。我们使用的TreeMap的Key为插入操作的值,Value为能够表示插入值的最小区间。例如,我们向map中插入2,用[2,2]能够表示,用[1,3]能够表示,用[-1000,1000]也能够表示,但是我们选择最小的区间[2, 2],这样做能做到题目要求的“目前为止看到的数字总结为不相交的区间列表“。 这里我们还用到了TreeMap提供的两个重要的操作floorEntry与ceilingEntry。floorEntry(k)返回小于等于k的最大元组;ceilingEntry(k)返回大于等于k的最小元组。我们记leftValInterval = map.floorEntry(val),rightValInterval = map.ceilingEntry(val)。 我们将插入的值与区间已有的值的关系分为图1的6种情况。case1、case3、case5表示已有的区间能够表示插入的值,其实case5能够和case1或case3合并。case2与case4表示插入值与已有的区间连续,那么将已有的区间扩大一个单元就能够表示插入值,例如向[1, 3]插入4,向[3, 4]插入2。case6表示如果有了插入值,就能够使得已有的左右区间连续,例如向[1, 4]和[6, 9]插入5。 如果我们清晰的分析出来这些情况,编写代码就不难了。对于新插入的值val,我们首先判断他们在TreeMap中是否存在,如果存在则返回。否则,查询val的floorEntry与ceilingEntry。如果floorEntry的右边界等于val-1,就说明我们可以将val合并到floorEntry对应的区间,将区间扩大,如图1中case2所示。对于ceilingEntry的处理同理,如图1中case4所示。如果floorEntry的右边界等于val-1且ceilingEntry的左边界等于val+1,说明我们将val插入到这两个区间后,能够使得这两个区间连续,如图1中case6所示。如果不满足图1中任何一个case,说明val无法被TreeMap中已有的区间无法表示,我们需要向TreeMap插入新区间[val, val]。 全部代码如下所示,时间复杂度O(nlogn),空间复杂度O(n)。

Read more

919. Meeting Rooms II [LintCode]

题目描述 给定一系列的会议时间间隔intervals,包括起始和结束时间[[s1,e1],[s2,e2],…] (si < ei),找到所需的最小的会议室数量。 样例1 样例2 https://www.lintcode.com/problem/meeting-rooms-ii/description 解法1 这种区间问题可以使用扫描线算法,我们将区间按照时间点排序,如果时间点相同,我们按照终点、起点顺序排序。这是因为在相同时间点上,当上一个会议结束后,该会议室就空出来了,在同一时间点的下一个会议就可以利用这个房间。例如时间段为{[1,5]、[5,10]},其实只需要一个会议室就够了,因为当[1,5]的会议结束后,[5,10]就可以利用这个房间。 图1绘制了扫描线算法的执行流程,实际上我们并不需要按照最细的时间粒度来扫描,我们只需要扫描每个区间的起始点与结束点。因为只有在这些时间点上,需要的房间数量才会发生变化。上面提到过,遇到相同的时间点,我们应当将end排在start前面,因为当上一个会议结束就会空出一个会议室,在这个时间点的下一个会议就可以利用这个房间。 在实现上,我们将起始与终止的时间点用一维数组表示,第0个元素是时间点,第1个元素表示起始还是终止,用0表示end,用1表示start。这样我们可以实现Comparator来排序,首先对比时间点,当时间点相同对比起止。当时间点数组排好序后,我们顺序扫描时间点,用parallel变量表示该时刻需要使用的会议室数量。遇到起始点时parallel++;遇到结束点时parallel–,parallel出现的最大值就是所需的最小会议室数量。 全部代码如下,时间复杂度O(nlogn),空间复杂度O(n)。

Read more

920. Meeting Rooms [LintCode]

题目描述 给定一系列的会议时间间隔,包括起始和结束时间[[s1,e1],[s2,e2],…(si < ei),确定一个人是否可以参加所有会议。 样例1 样例2 https://www.lintcode.com/problem/meeting-rooms/description 解法1 首先把时间段按照起始时间排序,如果存在任意的会议开始于前一个会议结束之前,则这个人无法参加所有回忆。我们将这种情况表示为,当∃ i ∈ [1, |intervals|),使得intervals[i-1].end > intervals[i].start则无法参加所有会议,否则能够参加所有会议。还有一个特殊的case要处理,那就是没有会议时,我们应当将这种情况认定为能够参加所有会议。因为不能参加全部会议只有一个标准,就是下一个会议开始时,上一个会议没有结束;否则就应当认定为能够参加全部会议。 全部代码如下,时间复杂度O(nlogn),空间复杂度O(1)。

Read more

57. 插入区间

题目 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 示例 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] 重叠。 https://leetcode-cn.com/problems/insert-interval/ 解法1 解法1的思路很简单,因为区间无重叠且按照起始点排序,那么我们可以借助56题的方法,先将newInterval插入到合适的位置,然后用56题方法合并区间。合适的位置指的是intervals[i].start <= newInterval.start但intervals[i+1].start > newInterval.start。 题目函数签名为“public int[][] insert(int[][] intervals, int[] newInterval) ”,因为插入新的区间会改变区间个数,使用int[][]不方便实现insert操作,所以我们使用容器List<int[]>来存放区间。题目要求结果存放在int[][]型数组中,我们在输出时还需要将List转换成Array。题目全部代码如下,时间复杂度O(n),空间复杂度O(n)。 解法2 解法2将intervals拆分成3部分,左半部分与newInterval没有交集,右半部分与newInterval没有交集,中间部分是与newInterval有交集的区间。假设前i个intervals中的区间与newInterval没有交集,第i+1个interval与newInterval有交集,我们将这两个区间合并形成[start, end],然后i++寻找下一个区间,直到找到与newInterval不相交的区间为止。此时,我们将合并后的区间[start, end]追加到结果集,然后将intervals中剩余的区间追加到结果集。 我们分析下interval[i]与newInterval不相交,但interval[i+1]与newInterval相交有哪些情况 图1列出了区间相交的集中情况。从图中可以看出,当intervals[i+1]与newInterval合并的时候,我们需要取两者左边界的最小值,右边界的最大值。 在合并的过程中,我们需要判断什么时候终止。如图2所示,终止条件是当newInterval的后沿小于第i+1个区间的前沿,即newInterval.end < intervals[i+1].start。那我们用不用判断newInterval的前沿与第i个区间后沿的关系呢?是不用的!因为前面我们提到,首先寻找与newInterval不相交的区间,加入到结果集,在这个过程中,我们的判断条件就是intervals[i].end < newIntervals.start。当发生合并的时候一定有intervals[i].end >=…

Read more

56. 合并区间

题目描述 给出一个区间的集合,请合并所有重叠的区间。 示例 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] 可被视为重叠区间。 https://leetcode-cn.com/problems/merge-intervals/ 解法1 为了便于描述,我们将区间记为interval,左边界记为interval.start, 右边界记为interval.end。我们将区间列表按照start排序,如果区间i与区间j相交,那么有interval[j].start <= interval[i].end(i<j)。 图1与图2绘制了区间合并的两种case,我们已经将区间列表按照start排序好了。图1中区间{1, 3}与{2, 6}相交,第二个区间的end=6大于第一个区间的end = 3,合并后区间为{1, 6}。图2中区间{1, 4}与区间{2, 3}相交,第二个区间的end=3小于第一个区间的end=4,合并后区间为{1, 4}。通过这两个case能够启发我们,如果区间i与区间j合并,那么合并后区间的end应该取二者较大的。 现在我们描述下算法流程,首先将第一个区间加入结果集,结果集是存放合并后区间的容器。然后遍历余下的每个区间(记为currInterval),我们取结果集最后一个区间(记为lastInterval),将currInterval与lastInterval对比,如果存在交集,将currInterval与lastInterval合并,合并后的区间写回lastInterval;如果不存在交集,将currInterval追加到结果集。 目前,leetcode-cn上这道题目的函数签名为“public List merge(List intervals) ”,但是实际上函数签名已经改为“public int[][] merge(int[][] intervals)”。intervals[i][0]代表第i个区间的左边界,intervals[i][1]代表第i个区间的右边界。下面是全部代码,因为涉及到排序,所以时间复杂度O(nlogn),空间复杂度O(n)。

Read more