索鸟网

  1. 首页
  2. 【LeetCode】C# 56、Merge Intervals

【LeetCode】C# 56、Merge Intervals


Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

合并区间。

思路:这个方法很巧妙,先把starts和ends单独拿出来排序,后通过if (i == n - 1 || starts[i + 1] > ends[i])来合并区间。

/**
 * Definition for an interval.
 * 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; }
 * }
 */
public class Solution {
    public IList<Interval> Merge(IList<Interval> intervals) {
        int n = intervals.Count();
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Array.Sort(starts);
        Array.Sort(ends);
        // loop through
        IList<Interval> res = new List<Interval>();
        for (int i = 0, j = 0; i < n; i++) { // j is start of interval.
            if (i == n - 1 || starts[i + 1] > ends[i]) {
                res.Add(new Interval(starts[j], ends[i]));
                j = i + 1;
            }
        }
        return res;
    }
}

来源地址:http://blog.csdn.net/qq_39643935/article/details/78227504 版权归作者所有!