LeetCode 56. Merge Intervals(合并区

给出一个区间的集合，请合并所有重叠的区间。

示例 :

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路:

• 将集合按照start属性数字进行排序
• 循环合并重叠区间
• 本题难度不高,但是可优化可操作的地方很多,另外,从隔壁获取了将对象按特定属性值排序的方法,感谢一波

代码:

    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() == 0)
            return intervals;
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        Interval ii, jj;
        for (int i = 0; i < intervals.size(); i++) {
            ii = intervals.get(i);
            for (int j = i + 1; j < intervals.size(); j++) {
                jj = intervals.get(j);
                if (ii.end >= jj.start) {
                    ii.end = Math.max(jj.end, ii.end);
                    intervals.remove(j);
                    j--;
                }
            }
        }
        return intervals;
    }

分析:

• 使用集合工具Collections.sort()进行排序,此处需要手动重写comparator()方法
• 简单的双循环遍历集合,在原地进行修改
• 由于start已经升序排序好了,只需要比较ii的尾节点与jj的头结点即可,同时区间修改也只需要获取最大的尾节点
• 由于是原地修改,需要删除多余的元素,并使j--防止遍历不完整

总结:

• 对象排序方法的学习,针对int类型等各类对象属性,能够提供更多解题思路
• 简单无脑的双循环还有很多能够优化的地方,这里就不多花时间了
• 原地修改需要注意指针的变化,循环的判断逻辑,防止越界等情况