合并区间算法示意

给定一堆区间，可能存在交集，对区间进行合并返回没有交集的区间集合。本文记录了这种问题的一种解法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Test2 {
    public static void main(String[] args) {
        int[][] intervals = new int[5][2];
        intervals[0] = new int[]{1,3};
        intervals[1] = new int[]{2,5};
        intervals[2] = new int[]{3,8};
        intervals[3] = new int[]{9,10};
        intervals[4] = new int[]{2,6};

        List<int[]> res = mergeIntervals(intervals);
        for (int[] arr : res) {
            System.out.println(Arrays.toString(arr));
        }
    }

    //合并区间,把多个有交集的区间进行合并，最后返回没有交集的区间集合
    // [[1,3],[2,5],[3,8],[9,10],[2,6]]
    public static List<int[]> mergeIntervals(int[][] intervals) {
        if (null == intervals) {
            throw new ArithmeticException("参数不能为null");
        }
        List<int[]> res = new ArrayList<>();
        if (intervals.length < 2) {
            res.add(new int[]{intervals[0][0], intervals[0][1]});
        }
        //按区间左端点升序排列
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int start = intervals[0][0];
        int end = intervals[0][1];
        int i=1;
        while(i< intervals.length) {
            int[] current = intervals[i];
            // 前一个区间的终点<下一个的起点,区间是断开的，[star,end]可以加入结果集
            if(end<current[0]) {
                res.add(new int[]{start,end});
                start = current[0];
                end =current[1];
            } else {
                //前一个和下一个有交集,修改end为前一个终点和下一个终点的最大值
                int max =Math.max(end,current[1]);
                end =max;
            }
            i++;
        }

        //合并结束，把start,end加入结果集
        res.add(new int[]{start,end});

        return res;
    }
}