13. Interval与扫描线
区间类的题目，很多可以用Greedy来做
Comparator的两种实现方法
一种是先Implements一个类，然后Arrays.sort(intervals, new newComparator);
public class newComparator implements Comparator<Object>{ public int compare(Object a, Object b) { Interval aa = (Interval) a; Interval bb = (Interval) b; return aa.start - bb.start; } }另一种是写在Arrays.sort()里面，实践证明这种更快
Arrays.sort(intervals, new Comparator<Interval>(){ //compare by start time public int compare(Interval a, Interval b){ return a.start - b.start; } });
这题最简单的方法就是sort by start time,then check if(intervals[i].start < intervals[i-1].end) return false;
Meeting Rooms II
给定一堆meetings, 要求返回需要最少room的数量
sort intervals by start time
minHeap compare with end time
for loop intervals, if cur.startTime < minHeap.peek().endTime, then push cur to heap, cnt++ ->NlogK
res = max(cnt)
class Solution {
public int minMeetingRooms(int[][] intervals) {
//sort intervals by start time ->NlogN
//minHeap compare with end time
//for loop intervals, if cur.startTime < minHeap.peek().endTime, then push cur to heap, cnt++ ->NlogK
//res = max(cnt)
//Time: NlogN
//Space: O(K)
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b) {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
}
});
PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
int res = 0;
for (int i = 0; i < intervals.length; i++) {
if (minHeap.isEmpty() || minHeap.peek()[1] > intervals[i][0]) {
minHeap.offer(intervals[i]);
} else {
minHeap.poll();
minHeap.offer(intervals[i]);
}
res = Math.max(res, minHeap.size());
}
return res;
}
}还有一种扫描线解法
Merge Interval
sort intervals by start time
iterate each interval, compare cur.startTime with prev.EndTime
if cur.startTime < end, then end = Math.max(end, cur.endTime)
else push [begin, end] to res
class Solution {
/*
sort intervals by start time
iterate each interval, compare cur.startTime with prev.EndTime
if cur.startTime < end, then end = Math.max(end, cur.endTime)
else push [begin, end] to res
*/
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return new int[0][0];
}
List<int[]> list = new ArrayList<>();
Arrays.sort(intervals, new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
int begin = intervals[0][0], end = intervals[0][1];
for (int i = 0; i < intervals.length; i++) {
if(intervals[i][0] <= end) {
end = Math.max(end, intervals[i][1]);
} else {
int[] interval = new int[2];
interval[0] = begin;
interval[1] = end;
list.add(interval);
begin = intervals[i][0];
end = intervals[i][1];
}
}
int[] interval = new int[2];
interval[0] = begin;
interval[1] = end;
list.add(interval);
int[][] res = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
res[i][0] = list.get(i)[0];
res[i][1] = list.get(i)[1];
}
return res;
}
//05/05/21, while loop
public int[][] merge(int[][] intervals) {
//sort interval by start time in ascending order
//[start,end], while (end >= curStart) -> end = curEnd and move to next
Arrays.sort(intervals, new Comparator<int[]> () {
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
List<int[]> list = new ArrayList<>();
int i = 0;
while (i < intervals.length) {
int start = intervals[i][0], end = intervals[i][1];
int j = i+1;
while (j < intervals.length && end >= intervals[j][0]) {
end = Math.max(end, intervals[j][1]);
j++;
}
int[] interval = new int[2];
interval[0] = start;
interval[1] = end;
list.add(interval);
i = j;
}
int[][] res = new int[list.size()][2];
for (int k = 0; k < list.size(); k++) {
res[k] = list.get(k);
}
return res;
}
}这题最简单的做法是把newInterval插到intervals里面，然后再调用上面的merge Interval的方法
但是鉴于此题有个前提Given a set of non-overlapping intervals，所以用merge interval的话可能会浪费很多时间
所以可以把intervals分成三部分，对于整个interval都在newinterval左边或者右边的我们可以直接add to res
所以只需要处理有overlapping的情况，这里有个技巧就是用while loop实现之前的三部分分类，改变newInterval的start和end值，直到当前的interval完全在newInterval的右边，没有任何交集
然后add newInterval, 再add the rest into res
这题对于space可以有优化，in place solultion,但是因为list.remove(i)是O(N)操作，所以时间上会有牺牲
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new LinkedList<>();
int i = 0;
while(i < intervals.size() && intervals.get(i).end < newInterval.start){
res.add(intervals.get(i));
i++;
}
while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
i++;
}
res.add(newInterval);
while(i < intervals.size()){
res.add(intervals.get(i));
i++;
}
return res;
}
}这题从算法上没啥好说的
就是注意corner case就好，比如[0,1] [7]
还有解体要有模块化的思路
public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res = new LinkedList<>();
if(nums == null || nums.length < 1) return res;
int start = nums[0];
int end = nums[0];
//int i = 1;
for(int i = 1; i < nums.length; i++){
if(nums[i - 1] + 1 != nums[i]){
String range = getRange(start, end);
res.add(range);
start = nums[i];
}
end = nums[i];
}
String last = getRange(start, end);
res.add(last);
return res;
}
//[2,3,4]
//[7]
private String getRange(int start, int end){
StringBuilder sb = new StringBuilder();
if(start == end){
sb.append(start);
}else if(start < end){
sb.append(start);
sb.append("->");
sb.append(end);
}
return sb.toString();
}
}Missing Ranges(好题)
这题比summary ranges稍难，重在理清思路
有个简单的方法是用lower做runner
每次遍历num时，设upperBelow = num - 1,然后比较upperBelow和 lower的关系
然后记得update lower = num + 1
这样写的话题有个test case过不去[2147483647], lower = 0, upper = 2147483647。原因在于lower = num + 1之后就int overflow了，所以必须cast to long type
public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> res = new LinkedList<>(); long low = (long) lower; long high = (long) upper; for(int num : nums){ // if(lower > upper) break; long upperBelow = (long)num - 1; if(low == upperBelow){ res.add((int)low + ""); }else if(low < upperBelow){ res.add((int)low + "->" + (int)upperBelow); } low = (long)num + 1; } if(low == high){ res.add((int)low + ""); }else if(low < high){ res.add((int)low + "->" + (int) high); } return res; }
Skyline Problem
Last updated
Was this helpful?