7/5, Interval 类，扫描线
7/5, Interval 类，扫描线
Interval 类问题中最常用的技巧，就是自定义 IntervalComparator，把输入按照 startTime 升序排序。
对于任意两个区间A与B，如果
A.end > B.start 并且
A.start < B.end
则 A 与 B 重叠。
按 start 排序后，数组有了单调性，上面的判断条件就简化成了 A.end > B.start 则一定重叠.
排序后的 Interval 扫描过程中，为了保证正确性，要格外小心多个 Interval 在同一 x 时，处理的先后顺序，比如 skyline problem.
熟悉下 TreeMap 的常用 API.
get()
put()
containsKey()
size()
values() : 返回 Collection<> of V
lowerKey(K key) ： 返回最大的小于参数的Key，没有则 null
higherKey(K key)：返回最小的大于参数的Key, 没有则 null
firstKey() : 返回最小 key
lastKey() : 返回最大 key
Trivial Problem.
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 个房间，这是错误的。
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 情况。
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 中。
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)
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.
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) 的。
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;
}一个比较简单的区间融合问题。
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;
动态更新 lower，维护当前有效 range.
时间复杂度 O(n).
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 的做法用时不相上下。
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 = 当前的有效数字个数。
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)
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 包含，无影响；
完全和其他 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) 排序，而后扫描。
当 x 值不同时，x 小的排在前面；
else 当 y 值不同时，y 小的排在前面；
调换的话下面的代码会有 bug
这题在九章课上讲的时候，使用的是 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)
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;
}
}Last updated
Was this helpful?