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] 可被视为重叠区间。

• 题目难度：中等。
• 英文网址：56. Merge Intervals 。
• 中文网址：56. 合并区间 。

思路分析

求解关键：题目要求将能够合并的“区间”都合并了，因此我们首先要先将“区间”集合按照区间的起始端点进行排序，起始端点小的区间靠前。 + 如果后一个区间的起始端点比前一个区间的终止端点还大（严格大，不等于），说明这两个区间不能合并。 + 否则，则说明这两个区间可以合并，合并以后的区间终止端点取当前区间的终止端点和前一个区间的终止端点中的最大者。

如果觉得 Collections.sort(intervals, Comparator.comparingInt((Interval a) -> a.start)); 这种 lambda 表达式的语法比较怪，可以使用如下两种等价的写法。

Collections.sort(intervals, (a, b) -> a.start - b.start);

Collections.sort(intervals, new Comparator<Interval>() {
    @Override
    public int compare(Interval o1, Interval o2) {
        return o1.start - o2.start;
    }
});

参考解答

参考解答1

import java.util.*;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class Solution {

    // 有点贪心算法的意思，所以一开始要对集合排序
    // 扫描线法

    public List<Interval> merge(List<Interval> intervals) {
        int len = intervals.size();
        if (len < 2) {
            return intervals;
        }

        Collections.sort(intervals, Comparator.comparingInt((Interval a) -> a.start));

        // 因为每次我们都拿最后一个元素，因此用栈是比较方便的
        Stack<Interval> stack = new Stack<>();
        stack.push(intervals.get(0));
        for (int i = 1; i < len; i++) {
            Interval curInterval = intervals.get(i);
            Interval peek = stack.peek();
            if (curInterval.start > peek.end) {
                stack.add(curInterval);
            } else {
                // 注意，这里应该取最大
                peek.end = Math.max(curInterval.end, peek.end);
            }
        }
        return stack;
    }

    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();

        Interval interval1 = new Interval(1, 3);
        Interval interval2 = new Interval(2, 6);
        Interval interval3 = new Interval(8, 10);
        Interval interval4 = new Interval(15, 18);

        intervals.add(interval1);
        intervals.add(interval2);
        intervals.add(interval3);
        intervals.add(interval4);

        Solution solution = new Solution();
        List<Interval> merge = solution.merge(intervals);
        for (Interval interval : merge) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0056-merge-intervals ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。