C#LeetCode刷题之#56-合并区间（Merge Intervals）

问题

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

输入: [[1,3],[2,6],[8,10],[15,18]]

输出: [[1,6],[8,10],[15,18]]

解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入: [[1,4],[4,5]]

输出: [[1,5]]

解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

Given a collection of intervals, merge all overlapping intervals.

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Input: [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

示例

public class Program {

    public static void Main(string[] args) {
        var intervals = new List<Interval> {
            { new Interval(1, 3) },
            { new Interval(2, 6) },
            { new Interval(8, 10) },
            { new Interval(15, 18) }
        };

        var res = Merge(intervals);
        ShowArray(res);

        Console.ReadKey();
    }

    private static void ShowArray(IList<Interval> list) {
        foreach(var num in list) {
            Console.Write($"({num.start},{num.end}) ");
        }
        Console.WriteLine();
    }

    public static IList<Interval> Merge(IList<Interval> intervals) {
        var res = new List<Interval>();
        if(intervals.Count == 0) return res;
        intervals = intervals.OrderBy(i => i.start).ToList();
        res.Add(intervals[0]);
        for(var i = 1; i < intervals.Count; i++) {
            if(intervals[i].start <= res[res.Count - 1].end) {
                res[res.Count - 1].end =
                Math.Max(intervals[i].end, res[res.Count - 1].end);
            } else {
                res.Add(intervals[i]);
            }
        }
        return res;
    }

    public class Interval {
        public int start;
        public int end;
        public Interval() { start = 0; end = 0; }
        public Interval(int s, int e) { start = s; end = e; }
    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

(1,6) (8,10) (15,18)

分析：

显而易见， 以上算法的时间复杂度为： 。