这题大概调试了有20多遍吧终于AC了；一开始是对题目理解有偏差（用了一个数组模拟map，想着如果数组里有这个范围就在数组里标记出来），发现思路错误之后就用后一项比前一项的做法，并且维护了一个isOverlapping标识来区分是否正在重叠；然后一直wrong answer，因为很多corner case没有cover到。最后就一遍遍改，增加对corner case的支持，写出的代码也很冗长。
class MyComparator implements Comparator<Interval> {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
}
public List<Interval> merge(List<Interval> intervals) {
List<Interval> res = new ArrayList<>();
if (intervals == null || intervals.size() == 0) return res;
Collections.sort(intervals, new MyComparator());
int curStart = 0, curEnd = 0;
int index = 0;
boolean isOverlapping = false;
while (index + 1 < intervals.size()) {
if (!isOverlapping) {
curStart = intervals.get(index).start;
curEnd = intervals.get(index).end;
}
if (intervals.get(index + 1).start <= intervals.get(index).end
|| intervals.get(index + 1).start <= curEnd) {
curEnd = Math.max(intervals.get(index + 1).end, curEnd);
isOverlapping = true;
} else {
isOverlapping = false;
res.add(new Interval(curStart, curEnd));
}
index++;
}
if (isOverlapping) {
res.add(new Interval(curStart, Math.max(intervals.get(intervals.size() - 1).end, curEnd)));
} else {
res.add(intervals.get(intervals.size() - 1));
}
return res;
}
发现一个不错的方法，分神的时候就用嘴说出来思路。昨天晚上一直走神，用这个方法才得以集中精力。
对于这种不涉及算法，动脑筋就能想出来的问题，知乎上这篇回答说得挺好的。这种题我总是很容易漏掉很多corner case。当面对一个个wrong anwser的时候很容易产生放弃心理，最后AC了看到别人的答案会觉得简洁得多，但我猜测别人也是经过很多调试才能绕过各种corner case的。。自己用了很多时间之后也不知道这种训练方式是否正确，但是AC之后真正觉得这题是自己做出来的。
我想引用Richardo博客习惯性的结尾签名了。
Always, good luck, Larry!
