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
163. Missing Ranges
个人印象比较深的一道题，在刚接触算法时研究过的。
第一种不太经济的写法是，建一个 boolean[upper - lower + 1] ，扫一遍数组记录下每个数是否出现过，然后根据 boolean[] 的 flag 进行融合。 这种写法首先需要 O(upper - lower) 的 extra space，而且最重要的是，没有利用到原数组 int[] 已经是排序了的性质，因此速度上不给力，而且在 upper = 100000000, lower = -10000000 这种极端情况下，空间占用非常大。
如果实现代码的时候发现要写很多 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> result = new ArrayList<>();
for (int num : nums) {
int justBelow = num - 1;
if (justBelow == lower) result.add(lower + "");
else if (lower < justBelow) result.add(lower + "->" + justBelow);
lower = num + 1;
}
if (lower == upper) result.add(lower + "");
else if (lower < upper) result.add(lower + "->" + upper);
return result;
}
}
然而，过不了corner case
我试了几次都过不去各种奇怪的corner case之后就放弃了，开始翻论坛的答案，震惊发现：
论坛答案竟然全部挂掉
我猜测原因是这几个坑爹的testcase比较新，最近才放上去，现在还没人针对新testcase写一个能够AC的答案出来。
稍微改了改，不太好看，但能AC而且没有用long转类型，在原来的基础上改成这样就可以了。回头刷的时候整理干净一点。
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<>();
for (int num : nums) {
if (num == Integer.MIN_VALUE) {
lower = num + 1;
continue;
}
int justBelow = num - 1;
if (justBelow == lower) result.add(lower + "");
else if (lower < justBelow) result.add(lower + "->" + justBelow);
if (num == upper) return result;
else lower = num + 1;
}
if (lower == upper) result.add(lower + "");
else if (lower < upper) result.add(lower + "->" + upper);
return result;
}
}
228. Summary Ranges
一个比较简单的区间融合问题。
两点注意：
Integer封装的使用，两个好处，一是不用担心边界值，MAX_VALUE和MIN_VALUE。二是最开始可以设置为null，好处理。Integer要注意用equals函数，就和String一样，char和int都是等于号和不等于号就能判断。
每次走到下一个需要处理的区间，才summary完上一个区间，所以for循环之后还要处理最后一个区间。
public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> result = new ArrayList<>();
if(nums == null || nums.length == 0) return result;
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)) result.add("" + start + "->" + end);
else result.add("" + start);
start = nums[i];
end = nums[i];
}
}
if (!start.equals(end)) result.add("" + start + "->" + end);
else result.add("" + start);
return result;
}
}
56. Merge Intervals
需要注意的是先进行对左端点排序，这样可以保证合并的顺序。
通过操作上一个区间右端点的值来合并，这样有一个好处，避免了连续合并区间时需要更新整个list的麻烦。使得合并的操作非常的自然，一直修改右端点就是一直合并区间，if-else的逻辑也避免了continue或者break的使用，很巧妙了。
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<>();
if (intervals == null || intervals.size() <= 1) return intervals;
Collections.sort(intervals, new IntervalComparator());
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); ++i) {
Interval curt = intervals.get(i);
if (curt.start <= prev.end) {
prev.end = Math.max(prev.end, curt.end);
} else {
result.add(prev);
prev = curt;
}
}
result.add(prev);
return result;
}
private class IntervalComparator implements Comparator<Interval>{
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
57. Insert Interval
这道题是Hard，直接做会不太好想。但是有前面的铺垫，顺着上一道的思路，就很简单。但可能并不是最优的解法。
先插入再排序，时间复杂度 O(nlogn) + O(n)
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (newInterval == null) return intervals;
if (intervals == null || intervals.size() == 0) {
intervals.add(newInterval);
return intervals;
}
List<Interval> result = new ArrayList<>();
intervals.add(newInterval);
Collections.sort(intervals, new IntervalComparator());
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); ++i) {
Interval curt = intervals.get(i);
if (curt.start <= prev.end) {
prev.end = Math.max(prev.end, curt.end);
} else {
result.add(prev);
prev = curt;
}
}
result.add(prev);
return result;
}
private class IntervalComparator implements Comparator<Interval>{
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
如果要进行进一步优化，要利用原题中 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;
}
252. Meeting Rooms
常规做法是将intervals数组排序，然后遍历，如果当前开始时间小于上一个结束时间，即为重合。
public boolean canAttendMeetings(Interval[] intervals) {
if (intervals == null)
return false;
// Sort the intervals by start time
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) { return a.start - b.start; }
});
for (int i = 1; i < intervals.length; i++)
if (intervals[i].start < intervals[i - 1].end)
return false;
return true;
}
另外有个数组的做法，运行速度特别快，原理就是利用数组的单调性。如果各个时间都不重合，那么他一定是单调递增的，比如【1，2】和【3，4】。那么将开始时间和结束时间分别排序后，i的开始时间必定大于i-1的结束时间。不然就必定有重合。
或者也可以理解为，对于每两个开始时间，中间必定有且仅有一个结束时间，不然就必定有重合。
public boolean canAttendMeetings(Interval[] intervals) {
int[] st=new int[intervals.length];
int[] ed=new int[intervals.length];
for(int i=0;i<intervals.length;i++){
st[i]=intervals[i].start;
ed[i]=intervals[i].end;
}
Arrays.sort(st);
Arrays.sort(ed);
for(int i=1;i<intervals.length;i++){
if(st[i]<ed[i-1])
return false;
}
return true;
}