题目描述

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

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]

输出: [[1,6],[8,10],[15,18]]

解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]

输出: [[1,5]]

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

解题思路

定义一个比较器，按照区间的起始值排序
使用上述比较器对区间集合进行排序
遍历区间集合，使用一个链表merged保存合并后的结果
- 如果当前区间和结果链表的尾部没有交集，就直接加入结果链表
- 如果当前区间和结果链表的尾部有交集，就先跟结果链表尾部合并一下
  - 合并方法：结果链表尾部的区间结束值取较大的那一个

Java 实现

private class IntervalComparator implements Comparator<Interval> {

    @Override

    public int compare (Interval a, Interval b) {

        return Integer.compare(a.start, b.start);

    }

}

public List<Interval> merge (List<Interval> intervals) {

    intervals.sort(new IntervalComparator());

    LinkedList<Interval> merged = new LinkedList<>();

    for (Interval interval : intervals) {

        if (merged.isEmpty() || interval.start > merged.getLast().end) {

            // 如果没有重叠的部分，就直接加入

            merged.add(interval);

        } else {

            // 如果有重叠的部分，就先合并一下

            merged.getLast().end = Math.max(merged.getLast().end, interval.end);

        }

    }

    return merged;

}

心得体会

这一题不是考察经典的排序算法，而是考察排序的应用。另外，定义比较器的代码也需要重视。

巴特西

【LeetCode】56-合并区间

题目描述

解题思路

Java 实现

心得体会

最新文章

热门文章