Merge Intervals

给定一个区间的集合, 合并所有重复的区间

 

my solution (12ms)

可以通过重新排序的形式来一步步合并, 比如:

start: 1 2 8 15

end: 3 6 10 18

其中 start 和 end 是经排序后的数组

从 1 开始, 如果接下来的开始下标小于当前的结束下标 (2 < 3)

那么, 就可以合并, 继续对比下一个. (8 < 6) 不成立, 那么第一个区间就出现了, 1-6

接下来从 8 开始, 继续以上步骤, 直至数组尾部, 这样算法的复杂度就是 O(n)

代码如上, 应该还有可以优化的地方 (比如说外围 for 循环, 他仅仅就是一个保留 i 的作用)

结果还不错

 

the best solution (8ms)

他的排序是直接在 Intervals 进行, 并且只比对 start (也是, 我好像做了多余的比对)

想法大致是一样的, 但是细节不够好