本文共 2254 字，大约阅读时间需要 7 分钟。

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

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

分析：

        我们先根据区间左端点排序，然后每个记录右端点为end。接下来我们一直和下一个小区间的左端点比较并更新end。

注意此处不能使用不稳定排序（自己实现的快排此处会gg）推使用jdk自带排序。

import java.util.*;/** * @author: Mr.Hu */public class Main {    public static void main(String[] args) {        Scanner sc =new Scanner(System.in);        Main main=new Main();        int n=sc.nextInt();        List
   
     list=new LinkedList<>();        List
    
      list1=new LinkedList<>();        for (int i = 0; i < n; i++) {            Interval t=new Interval(sc.nextInt(),sc.nextInt());            list.add(t);        }        list1=main.merge(list);    }    static class  Interval {          int start;          int end;          Interval() { start = 0; end = 0; }          Interval(int s, int e) { start = s; end = e; }      }        public List
     
       merge(List
      
        intervals) { //*56. 合并区间                if (intervals.isEmpty()) return intervals;                //quickSort(intervals,0,intervals.size()-1); //快排不稳定                Collections.sort(intervals, new Comparator
       
        () {                    @Override                    public int compare(Interval o1, Interval o2) {  //必须有返回0的情况，否则报错                        if ( o1.start>o2.start) return 1;                        else if (o1.start==o2.start)return 0;                        else return -1;                    }                });            List
        
          list=new LinkedList<>(); for (int i = 0; i < intervals.size(); i++) { //遍历整个list Interval a=new Interval(); a.start=intervals.get(i).start; int end=intervals.get(i).end; // 可能存在嵌套 while (i
         
          =intervals.get(i+1).start){ //目前区间最大end 大于下一个开始 end=Math.max(intervals.get(i+1).end,end); i++; } a.end=end; list.add(a); } return list; }/**********以下为自己实现的快排******/ private void swap(int i,int j,List
          
            list){ Interval temp=list.get(i); list.set(i,list.get(j)); list.set(j,temp); } private void quickSort(List
           
             list,int start,int end){ //此题要求稳定排序 if (start>=end) return; int i=start,j=end; int pivot=list.get(start).start; swap(i,end,list); //基准放到最后 while (true){ while (i
            
             <=pivot) i++; //小于等于 while (i
             
              =pivot) j--; if (i
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/h2453532874/article/details/88727652 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！