合并区间

Merge Intervals

问题：合并区间

考察：数组、排序

来源：DSA Prep / Citadel

链接：https://www.dsaprep.dev/blog/merge-intervals-leetcode-solution

Problem: Merge Intervals

Patterns: Array, Sorting

Recency: 3mo

Link: https://www.dsaprep.dev/blog/merge-intervals-leetcode-solution

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：先按区间起点排序。依次扫描区间，若当前区间与结果最后一个重叠，就扩展结束点；否则开启新区间。

复杂度：排序 O(n log n)，扫描 O(n)，空间 O(n) 输出。