
问题
给出一个区间的集合,请合并所有重叠的区间。
输入: [[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)
分析:
显而易见, 以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3676。