力扣(LeetCode)56

水深无声 2022-03-07 14:20 154阅读 0赞

题目地址：  
[https://leetcode-cn.com/probl...][https_leetcode-cn.com_probl...]  
题目描述：  
给出一个区间的集合，请合并所有重叠的区间。

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

解答：  
按照区间起始节点排序。  
然后合并即可，这题难的是怎么写出完美的合并代码。  
判断逻辑是如果ans列表为空或者ans列表最后一个区间和当前区间不相交就加入当前区间。  
否则把ans列表最后一个区间和当前区间合并。

java ac代码：

/**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            
            Collections.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    if(o1.start != o2.start)
                    return o1.start-o2.start;
                    return o1.end-o2.end;
                }
            });
            List<Interval> ans = new ArrayList(intervals.size());
            for(int i = 0;i < intervals.size();i++)
                if(ans.size() == 0||ans.get(ans.size()-1).end < intervals.get(i).start)
                    ans.add(intervals.get(i));
            else
                ans.get(ans.size()-1).end =Math.max(intervals.get(i).end,ans.get(ans.size()-1).end    );
            return ans;
            
            
        }
    }

[https_leetcode-cn.com_probl...]: https://leetcode-cn.com/problems/merge-intervals/