后端开发刷题 | 合并区间

描述

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

请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0≤n≤2×105，区间内 的值都满足 0≤val≤2×105

示例1

输入：

[[10,30],[20,60],[80,100],[150,180]]

返回值：

[[10,60],[80,100],[150,180]]

示例2

输入：

[[0,10],[10,20]]

返回值：

[[0,20]]

思路分析：

该题可以使用贪心算法解决，找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

步骤：

1.先把这些区间进行排序，使用 Collections.sort()方法

2.根据前一个区间的end小于当前区间的start，区间不重叠；反之则重叠。

3.将这些区间添加到res里面，最终返回res

代码分析：

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 
     * @param intervals Interval类ArrayList 
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        ArrayList<Interval> res=new ArrayList<>();
        //特殊情况
        if(intervals.size()==0) return res;
        //按区间进行排序
        Collections.sort(intervals,(o1,o2)->o1.start-o2.start);
        //把排序后的第一个区间放入res
        res.add(intervals.get(0));
        int before=0;
        for(int i=1;i<intervals.size();i++){
            Interval o1=intervals.get(i);
            Interval origin=res.get(before);

            //区间不重叠，前一个区间的end小于当前区间的start
            if(origin.end<o1.start){
                //添加
                res.add(o1);
                before++;
            }else{
                //区间重叠，前一个区间的end大于当前区间的start
                res.remove(before);
                Interval s=new Interval(origin.start,Math.max(origin.end,o1.end));
                res.add(s);
            }
        }
        return res;

    }
}

原文地址：https://blog.csdn.net/jingling555/article/details/142438199

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！