索鸟网

  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 版权归作者所有!

相关教程

  • 【Leetcode】【python】Merge Intervals

    题目大意 给出多个数据区段,把首尾相连的数据段合并。 注意点: 所给的数据段是乱序的 解题思路 把起始位置(start)排序。遍历数据段,并与结果集中最后一个数据段比较能否合并,如果能合并就合并,否则加入结果集。 代码 # Definition for an interval. # class Interval(object): # def __init__(self,
  • leetcode56 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]. 输入一系列区间,将出现交叉的区间合并起来,并将合并后的区间
  • LeetCode56. Merge Intervals

    LeetCode56. 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,1
  • Leetcode [Merge Two Sorted Lists]

    Problem : Merge Two Sorted Lists Question Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 思路 直接用栈解决。比较
  • 【LeetCode】617. Merge Two Binary Trees

    题目描述 Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge t
  • [leetcode] 21. Merge Two Sorted Lists

    Question: Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Solution: 直接模拟归并排序的合并部分,不过对象是链表指针,但是过程是一样的。
  • 【LeetCode】C# 46、Permutations

    Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1],
  • Leetcode题解-21. Merge Two Sorted Lists

    Leetcode题解-21. Merge Two Sorted Lists Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists(把两个