7/5, Interval 类,扫描线
Interval 类问题中最常用的技巧,就是自定义 IntervalComparator,把输入按照 startTime 升序排序。
对于任意两个区间A与B,如果
按 start 排序后,数组有了单调性,上面的判断条件就简化成了 A.end > B.start 则一定重叠.
排序后的 Interval 扫描过程中,为了保证正确性,要格外小心多个 Interval 在同一 x 时,处理的先后顺序,比如 skyline problem.
熟悉下 TreeMap 的常用 API.
get()
values() : 返回 Collection<> of V
lowerKey(K key) : 返回最大的小于参数的Key,没有则 null
higherKey(K key):返回最小的大于参数的Key, 没有则 null
Trivial Problem.
Copy public class Solution {
private class IntervalComparator implements Comparator < Interval >{
public int compare ( Interval a , Interval b){
return a . start - b . start ;
}
}
public boolean canAttendMeetings ( Interval [] intervals) {
if (intervals == null || intervals . length <= 1 ) return true ;
Arrays . sort (intervals , new IntervalComparator() );
for ( int i = 1 ; i < intervals . length ; i ++ ){
if (intervals[i] . start < intervals[i - 1 ] . end ) return false ;
}
return true ;
}
}
fb 面经高频题,follow up 是返回那个 overlap 最多的区间。
另一个
fb onsite 面经题 里,首先给 n 个一维 interval,返回任意重合最多的点;然后给 n 个二维 rectangle,返回任意重复最多的点。
扫描线算法。需要注意的是如果有两个 interval 首尾相接,要把结束的那个排在 array 的前面,先把房间腾出来;否则的话会认为收尾相接的两个 meeting 需要占 2 个房间,这是错误的。
Copy public class Solution {
private class Point {
int time;
boolean isStart;
public Point ( int time , boolean isStart){
this . time = time;
this . isStart = isStart;
}
}
private class PointComparator implements Comparator < Point >{
public int compare ( Point a , Point b){
if ( a . time == b . time ) return a . isStart ? 1 : - 1 ;
else return a . time - b . time ;
}
}
public int minMeetingRooms ( Interval [] intervals) {
if (intervals == null || intervals . length == 0 ) return 0 ;
Point [] arr = new Point [ intervals . length * 2 ];
for ( int i = 0 ; i < intervals . length ; i ++ ){
arr[i * 2 ] = new Point(intervals[i] . start , true ) ;
arr[i * 2 + 1 ] = new Point(intervals[i] . end , false ) ;
}
Arrays . sort (arr , new PointComparator() );
int maxOverLap = 0 ;
int curCount = 0 ;
for ( Point pt : arr){
if ( pt . isStart ) curCount ++ ;
else curCount -- ;
maxOverLap = Math . max (maxOverLap , curCount);
}
return maxOverLap;
}
}
(FB) follow-up: 如何返回重叠最多的那个区间?
当前 maxOverlap 创造新高的时候,存下 start 的时间戳,因为这是所有重合区间中 start 时间最晚的一个;
继续扫描,看到新的 end 的时候,存下这个 end 的时间戳,因为它是重合区间里 end 时间最早的一个;
二者之间,就是具体的 max overlap 区间。
针对这题还有另外一种写法,用 heap / PriorityQueue,相比之下代码量要小一点,不过不像扫描线算法那样清晰易于理解,而且容易进行修改适应各种 follow-up 情况。
Copy public class Solution {
private class IntervalComparator implements Comparator < Interval >{
public int compare ( Interval a , Interval b){
return a . start - b . start ;
}
}
public int minMeetingRooms ( Interval [] intervals) {
if (intervals == null || intervals . length == 0 ) return 0 ;
Arrays . sort (intervals , new IntervalComparator() );
PriorityQueue < Integer > heap = new PriorityQueue < Integer >();
heap . offer (intervals[ 0 ] . end );
int maxOverLap = 1 ;
for ( int i = 1 ; i < intervals . length ; i ++ ){
if (intervals[i] . start < heap . peek ()){
maxOverLap ++ ;
} else {
heap . poll ();
}
heap . offer (intervals[i] . end );
}
return maxOverLap;
}
}
这题需要注意的 corner case 有两个:
按 startTime 排序后, merge 的新 interval 可能是完全包含于前一个 interval 的,如 【1,4】,【2,3】. 所以当发现 overlap 时,新的 End 要以两个 end 的最大值为准。
记得循环尾部做一个收尾,把最后 merge 完的结果生成新的 interval 也加到 list 中。
Copy public class Solution {
private class IntervalComparator implements Comparator < Interval >{
public int compare ( Interval a , Interval b){
return a . start - b . start ;
}
}
public List < Interval > merge ( List < Interval > intervals) {
List < Interval > list = new ArrayList < Interval >();
if (intervals == null || intervals . size () == 0 ) return list;
Collections . sort (intervals , new IntervalComparator() );
int curStart = intervals . get ( 0 ) . start ;
int curEnd = intervals . get ( 0 ) . end ;
for ( int i = 1 ; i < intervals . size (); i ++ ){
Interval cur = intervals . get (i);
if ( cur . start > curEnd){
list . add ( new Interval(curStart , curEnd) );
curStart = cur . start ;
curEnd = cur . end ;
} else {
curEnd = Math . max (curEnd , cur . end );
}
}
list . add ( new Interval(curStart , curEnd) );
return list;
}
}
顺着上一题的思路,一个最简单直接的写法就是。。直接把新的 interval 插进去,然后再跑一遍 merge interval 的代码。
考虑到一些极端情况,比如 newInterval 合并了原始 list 中绝大多数 intervals, 在原 list 上进行操作的话需要的比较与删减也会很多,所以从算法复杂度上讲,这种写法至少可以 AC,但不是最优。
时间复杂度 O(n log n ) + O(n)
Copy public class Solution {
private class IntervalComparator implements Comparator < Interval >{
public int compare ( Interval a , Interval b){
return a . start - b . start ;
}
}
public List < Interval > insert ( List < Interval > intervals , Interval newInterval) {
intervals . add (newInterval);
Collections . sort (intervals , new IntervalComparator() );
List < Interval > list = new ArrayList < Interval >();
int curStart = intervals . get ( 0 ) . start ;
int curEnd = intervals . get ( 0 ) . end ;
for ( int i = 1 ; i < intervals . size (); i ++ ){
Interval cur = intervals . get (i);
if ( cur . start > curEnd){
list . add ( new Interval(curStart , curEnd) );
curStart = cur . start ;
curEnd = cur . end ;
} else {
curEnd = Math . max (curEnd , cur . end );
}
}
list . add ( new Interval(curStart , curEnd) );
return list;
}
}
如果要进行进一步优化,要利用原题中 set of "non-overlapping" intervals 的条件,所以 newInterval 有可能会与任何 interval 或 N 个 interval 的集合,在左右两边 merge [0, N] 个 interval, 从完全 disjoint 到完全合并。
时间复杂度 O(n),one-pass.
Copy public List< Interval > insert( List< Interval > intervals , Interval newInterval) {
List < Interval > list = new ArrayList <>();
int ptr = 0 ;
int n = intervals . size ();
while (ptr < n && intervals . get (ptr) . end < newInterval . start ) list . add ( intervals . get (ptr ++ ));
while (ptr < n && intervals . get (ptr) . start <= newInterval . end ){
newInterval . start = Math . min ( newInterval . start , intervals . get (ptr) . start );
newInterval . end = Math . max ( newInterval . end , intervals . get (ptr) . end );
ptr ++ ;
}
list . add (newInterval);
while (ptr < n) list . add ( intervals . get (ptr ++ ));
return list;
}
在此基础上还可以进一步优化,不用额外空间,on-the-fly 解决战斗。
这种做法可以不花费任何额外空间,但是时间复杂度会更高,因为 List.remove() 是一个 O(n) 操作,add(index, val) 也是 O(n) 的。
Copy public List< Interval > insert( List< Interval > intervals , Interval newInterval) {
int ptr = 0 ;
while (ptr < intervals . size () && intervals . get (ptr) . end < newInterval . start ) ptr ++ ;
while (ptr < intervals . size () && intervals . get (ptr) . start <= newInterval . end ){
newInterval . start = Math . min ( newInterval . start , intervals . get (ptr) . start );
newInterval . end = Math . max ( newInterval . end , intervals . get (ptr) . end );
intervals . remove (ptr);
}
intervals . add (ptr , newInterval);
return intervals;
}
一个比较简单的区间融合问题。
Copy public class Solution {
public List < String > summaryRanges ( int [] nums) {
List < String > list = new ArrayList <>();
if (nums == null || nums . length == 0 ) return list;
Integer start = null ;
Integer end = null ;
for ( int i = 0 ; i < nums . length ; i ++ ){
if (start == null ){
start = nums[i];
end = nums[i];
} else if (nums[i] == end + 1 ){
end ++ ;
} else {
if ( ! start . equals (end)) list . add ( "" + start + "->" + end);
else list . add ( "" + start);
start = nums[i];
end = nums[i];
}
}
if ( ! start . equals (end)) list . add ( "" + start + "->" + end);
else list . add ( "" + start);
return list;
}
}
第一种不太经济的写法是,建一个 boolean[upper - lower + 1] ,扫一遍数组记录下每个数是否出现过,然后根据 boolean[] 的 flag 进行融合。 这种写法首先需要 O(upper - lower) 的 extra space,而且最重要的是,没有利用到原数组 int[] 已经是排序了的性质,因此速度上不给力,而且在 upper = 100000000, lower = -10000000 这种极端情况下,空间占用非常大。
改进后的代码实现过程中,最开始没有考虑全 test case,虽然AC 了但是代码不够 clean. 下面参考论坛里的解法就简明了很多。
如果实现代码的时候发现要写很多 if else 处理特殊情况,最好的选择还是暂停一下,多把 test case 思考全再动手。
【lower, nums[i] - 1】 范围内没有数, ADD;
【nums[last] + 1,upper】 范围内没有数, ADD;
时间复杂度 O(n).
Copy public class Solution {
public List < String > findMissingRanges ( int [] nums , int lower , int upper) {
List < String > list = new ArrayList < String >();
for ( int n : nums){
int justBelow = n - 1 ;
if (lower == justBelow) list . add (lower + "" );
else if (lower < justBelow) list . add (lower + "->" + justBelow);
lower = n + 1 ;
}
if (lower == upper) list . add (lower + "" );
else if (lower < upper) list . add (lower + "->" + upper);
return list;
}
}
作为一个 data structure design 题,首先要问好到底哪个 API call 比较频繁,设计上倾向于优化哪个操作。
先写了个略粗糙的版本,维护当前所有 interval 的 list,每次插入操作的时候靠 binary search 找每个 val 的位置,然后分情况考虑。
addNum(int val) 时间复杂度 O(log n) + O(n)
getInterval() 时间复杂度 O(1)
空间复杂度 O(n)
n = 当前有效数字个数
在测试数据集上,这个方法和 TreeMap 的做法用时不相上下。
Copy public class SummaryRanges {
List < Interval > list;
/** Initialize your data structure here. */
public SummaryRanges () {
list = new ArrayList < Interval >();
}
public void addNum ( int val) {
if ( list . size () == 0 ){
list . add ( new Interval(val , val) );
} else {
if ( list . size () == 1 ){
if (val <= list . get ( 0 ) . end && val >= list . get ( 0 ) . start ){
return ;
}
}
if (val < list . get ( 0 ) . start ){
if (val == list . get ( 0 ) . start - 1 ){
list . get ( 0 ) . start = val;
} else {
list . add ( 0 , new Interval(val , val) );
}
return ;
} else if (val > list . get ( list . size () - 1 ) . end ){
if (val == list . get ( list . size () - 1 ) . end + 1 ){
list . get ( list . size () - 1 ) . end = val;
} else {
list . add ( new Interval(val , val) );
}
return ;
}
int pos = binarySearch(list , val) ;
int prevEnd = list . get (pos) . end ;
int nextStart = list . get (pos + 1 ) . start ;
if (val <= prevEnd || val >= nextStart){
return ;
} else if (val == prevEnd + 1 && val == nextStart - 1 ){
list . get (pos) . end = list . get (pos + 1 ) . end ;
list . remove (pos + 1 );
} else if (prevEnd + 1 >= val){
list . get (pos) . end = Math . max ( list . get (pos) . end , val);
} else if (val == nextStart - 1 ){
int newStart = list . get (pos + 1 ) . start - 1 ;
int newEnd = list . get (pos + 1 ) . end ;
// Will have MLE if don't remove
list . remove (pos + 1 );
list . add (pos + 1 , new Interval(newStart , newEnd) );
} else {
list . add (pos + 1 , new Interval(val , val) );
}
}
}
public List < Interval > getIntervals () {
return list;
}
private int binarySearch ( List < Interval > list , int val){
int left = 0 ;
int right = list . size () - 1 ;
while (left + 1 < right){
int mid = left + (right - left) / 2 ;
if ( list . get (mid) . start == val){
return mid;
} else if ( list . get (mid) . start < val){
left = mid;
} else {
right = mid;
}
}
return left;
}
}
第二个版本,自己写了个 LinkedList 维护目前所有数字,每次 call getIntervals() 的时候根据 list 当场生成。
addNum(int val) 时间复杂度 O(n);
getIntervals() 时间复杂度 O(n);
空间:O(n);
n = 当前的有效数字个数。
Copy public class SummaryRanges {
private class Node {
Integer val;
Node next;
public Node ( Integer val){
this . val = val;
this . next = null ;
}
}
Node head;
/** Initialize your data structure here. */
public SummaryRanges () {
Node dummy = new Node( null ) ;
head = dummy;
}
public void addNum ( int val) {
Node cur = head . next ;
Node prev = head;
while (cur != null ){
if ( cur . val == val) return ;
if ( cur . val > val){
prev . next = new Node(val) ;
prev . next . next = cur;
return ;
}
prev = cur;
cur = cur . next ;
}
prev . next = new Node(val) ;
}
public List < Interval > getIntervals () {
List < Interval > list = new ArrayList < Interval >();
Node cur = head . next ;
Integer curStart = null ;
Integer curEnd = null ;
while (cur != null ){
int val = cur . val ;
if (curStart == null && curEnd == null ){
curStart = val;
curEnd = val;
} else {
if (val == curEnd + 1 ){
curEnd = val;
} else {
list . add ( new Interval(curStart , curEnd) );
curStart = val;
curEnd = val;
}
}
cur = cur . next ;
}
list . add ( new Interval(curStart , curEnd) );
return list;
}
}
参考了论坛代码之后,另一种巧妙的做法:
addNum(int val) 时间复杂度:O(log n)
getIntervals() 时间复杂度:o(n log n)
空间复杂度: O(n)
Copy public class SummaryRanges {
TreeMap < Integer , Interval > tree;
public SummaryRanges () {
tree = new TreeMap <>();
}
public void addNum ( int val) {
if ( tree . containsKey (val)) return ;
Integer l = tree . lowerKey (val);
Integer h = tree . higherKey (val);
if (l != null && h != null && tree . get (l) . end + 1 == val && h == val + 1 ) {
// Joining two intervals
tree . get (l) . end = tree . get (h) . end ;
tree . remove (h);
} else if (l != null && tree . get (l) . end + 1 >= val) {
// Completely contained in left interval
// Try to expand end
tree . get (l) . end = Math . max ( tree . get (l) . end , val);
} else if (h != null && h == val + 1 ) {
// Right next to right interval
// Merge
tree . put (val , new Interval(val , tree . get(h) . end ) );
tree . remove (h);
} else {
// Disjoint new interval
tree . put (val , new Interval(val , val) );
}
}
public List < Interval > getIntervals () {
return new ArrayList <>( tree . values ());
}
}
(FB) 给定的是 stream of intervals,求 cover range.
这么改了之后难了很多。。用 TreeMap 依然可以,但是假设目前 TreeMap 维护的都是 none-overlapping intervals,一个新 interval 加入之后可能会出现若干种情况:
完全和其他 interval disjoint,插入即可;
和左边的 overlap,但是不和右边的 overlap;
和右边的 overlap,但是不和左边的 overlap;
一次跨了多个 interval,这里面就有全包括的,包括一半的,在左边搭边的,在右边搭边的。。。
于是我觉得这题用 TreeMap 比较和乎人性的做法是,TreeMap 只负责维护 sorted intervals,需要查询 coverage 的时候,直接 new ArrayList<>(treeMap.values()) 给导出来然后跑一遍 merge interval ..
或者,直接维护一个按照 start time 排好序的 disjoint list of intervals,然后每次新的 interval 过来的时候,就 in-place 扫一遍做 merge 好了~ 这样每次 insert O(N),getCoverage O(1)
扫描线算法,因为 building outline 只可能发生在每一段 "start/end" 的边界上,因此以每个 edge 的 (x, height) 排序,而后扫描。
这题在九章课上讲的时候,使用的是 HashHeap,我们需要一个 maxHeap 来检测对于每一个点,我们建筑的最大高度,但同时在扫描过程中我们需要对每一个具体的 edge 进行删除操作,而 HashHeap 可以做到 O(log n) 的复杂度,Java 默认的 heap 只能做到 O(n).
如何在 heap 中快速删除这个问题和当初准备 Bloomberg 时候的马拉松问题一样,Java 中有现成的解决方案:
TreeMap.
接下来的问题是:
当遇到一座楼的右边界时,如何删除其对应的左边界?在 TreeMap 里直接用 Edge class 做 key 是不行的,因为我们无法通过 new 一个参数一模一样的 instance 去做 lookup. 所以在 Key-Value 的设计中,我们应该用 height 做 Key,因为同一座建筑左右墙 height 相等,就可以实现查找。即使有多座 height 一样的左墙,我们也只需要用 count 做 value,把当前 height 的墙数减一即可。
对于同一高度的不同建筑,如何确保其在 TreeMap 中不会互相 replace ,从而保证算法的正确性? 在自己 debug 的过程中,即使后面逻辑完全一致,不用负数 height 做 Key 依然会有 bug. ,用负数可以省去 Edge class 里面一个变量,最主要的是,在调用 Arrays.sort() 时,可以保证对于同一个 x 位置,在增加时永远先处理 height 最高的建筑,而删除时永远先删除 height 最小的建筑,从而保证了在同一个高度上多个建筑 Edge 重叠时,算法的正确性。
如何正确处理建筑清光之后,剩余高度为 0 的情况?一开始在 TreeMap 里加一个 (0, 1) 的 entry,代表始终有一个高度为 0 的墙,即地面;
O(Edge 排序) + O(Edge 数 * (插入 / 删除 + 查找))
O(2n log 2n) + O(2n * (log 2n + log 2n)) = O(n log n)
Copy public class Solution {
private class Edge implements Comparable < Edge >{
int x;
int y;
public Edge ( int x , int y){
this . x = x;
this . y = y;
}
public int compareTo ( Edge b){
// Ascending in x coordinate
if ( this . x != b . x ) return this . x - b . x ;
else return this . y - b . y ;
}
}
public List < int []> getSkyline ( int [][] buildings) {
// Key : height of edge
// Value : count of edges of that height
TreeMap < Integer , Integer > treeMap = new TreeMap <>();
List < int []> list = new ArrayList <>();
Edge [] edges = new Edge [ 2 * buildings . length ];
for ( int i = 0 ; i < buildings . length ; i ++ ){
int [] building = buildings[i];
edges[i * 2 ] = new Edge(building[ 0 ] , - building[ 2 ]) ;
edges[i * 2 + 1 ] = new Edge(building[ 1 ] , building[ 2 ]) ;
}
Arrays . sort (edges);
treeMap . put ( 0 , 1 );
int prevHeight = 0 ;
for ( Edge edge : edges){
if ( edge . y < 0 ){
if ( ! treeMap . containsKey ( - edge . y )){
treeMap . put ( - edge . y , 1 );
} else {
int count = treeMap . get ( - edge . y );
treeMap . put ( - edge . y , count + 1 );
}
} else {
int count = treeMap . get ( edge . y );
if (count == 1 ){
treeMap . remove ( edge . y );
} else {
treeMap . put ( edge . y , count - 1 );
}
}
int curHeight = treeMap . lastKey ();
if (prevHeight != curHeight){
list . add ( new int []{ edge . x , curHeight});
prevHeight = curHeight;
}
}
return list;
}
}