合并区间

难度：中等

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例1

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]

示例2

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]]

题解

基于区间左边界完成数组升序排序 遍历数组：若区间右边界小于后继区间左边界，直接将当前区间添加到结果数组中，否则更新后继区间的左边界为当前区间左边界，若当前区间右边界小于后继区间右边界，继续循环；否则更新当前区间右边界为后继区间的右边界 将数组最后一个区间添加到数组中。

想法代码

public class Solution
{
    public static void Main(string[] args)
    {
        int[][] intervals =
        {
            new[] { 1, 3 },
            new[] { 2, 6 },
            new[] { 8, 10 },
            new[] { 15, 18 }
        };
        Solution solution = new Solution();
        int[][] res = solution.Merge(intervals);
        foreach (var i in res)
        {
            foreach (var j in i)
            {
                Console.Write(j + " ");
            }
            Console.WriteLine();
        }
    }

    public int[][] Merge(int[][] intervals)
    {
        if (intervals.Length == 0)
        {
            return intervals;
        }
        intervals = intervals.OrderBy(p => p[0]).ToArray();

        List<int[]> list = new List<int[]>();
        for (int i = 0; i < intervals.Length - 1; i++)
        {
            if (intervals[i][1] >= intervals[i + 1][0])
            {
                intervals[i + 1][0] = intervals[i][0];

                if (intervals[i][1] >= intervals[i + 1][1])
                {
                    intervals[i + 1][1] = intervals[i][1];
                }
            }

            else
            {
                list.Add(intervals[i]);
            }
        }

        list.Add(intervals[intervals.Length - 1]);

        int[][] result = list.ToArray();
        return result;
    }
}