LeetCode刷题191123

博主渣渣一枚，刷刷leetcode给自己瞅瞅，大神们由更好方法还望不吝赐教。题目及解法来自于力扣（LeetCode），传送门。

算法：

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

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

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

　　刷题以来第一次比较顺利的做出来，并且效率还可以，嘻嘻。

public class Solution {

public int[][] Merge(int[][] intervals)

        {

            var outBegin = ;

            var outNext = ;

            var result = new List<int[]>();

            intervals = intervals.OrderBy(x => x[]).ToArray();

            while (outNext < intervals.Length)

            {

                if (result.FirstOrDefault() != null && result[outBegin][] >= intervals[outNext][])

                {

                    outNext++;

                    continue;

                }

                if (result.FirstOrDefault() == null)

                {

                    result.Add(intervals[]);

                }

                else if (result[outBegin][] >= intervals[outNext][])

                {

                    result[outBegin][] = intervals[outNext][];

                }

                else

                {

                    result.Add(intervals[outNext]);

                    outBegin++;

                }

                outNext++;

            }

            return result.ToArray();

        }

}

　　思路其实是受了昨天刷题官方解法的启发，滑动窗口。与之前一样，有一些特殊情况需要额外处理一下，如{[1,4],[2,3]}，这种情况下[2,3]其实是包含在[1,4]内部的，所以其实输出的结果还是[1,4]。又如[2,4],[1,4]这种例子，如果只是简单的循环不排序的话，容易产生[2,4],[1,4]这样两个区间的错误答案。

　　官方解法传送门：https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode/

　　官方提供了两种解法，第一种暴力穷举的方式就不谈了。第二种其实和上面的滑动窗口的思路类似。

巴特西

LeetCode刷题191123

最新文章

热门文章