leetcode Sort

leetcode 56题

Posted by franki on June 20, 2021

leetcode 56题 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例1

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

示例2

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

思路

排序

代码

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (intervals.length === 1) {
        return intervals;
    }
    intervals.sort((a, b) => a[0] - b[0]);
    const res = [intervals[0]];
    let curIndex = 0;
    for (let i=1; i<intervals.length; i++) {
        if (intervals[i][0] > res[curIndex][1]) {
            res.push(intervals[i]);
            curIndex++;
        } else {
            res[curIndex][1] = Math.max(res[curIndex][1], intervals[i][1]);
        }
    }
    return res;
};

复杂度分析:

  • 时间复杂度: O(N)
  • 空间复杂度：O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS