求问一道算法题的思路

Q: 给一组intervals。求non-overlapping intervals。每个subarray都已经sort好
举例：
[
  [[1, 3], [6, 7]],.
  [[2, 4]],
  [[2, 3], [9, 12]].鐣欏?
]
返回. visit 1point3acres.com for more.
[[4, 6], [7, 9]]
因为跟Leetcode拿到merge intervals太像了...老跑偏求所有merge overlapping之后再求Non-overlapping...但觉得真相远远不是这样...求高手给思路(附加一些注释就更好了） 谢谢！

这题分两块：

1. merge k sorted array
其实也不用merge k sorted array，但是你得用merge k sorted array的思路，依次把当前最小的interval拿出来，这样才能做下一步
2. merge intervals
其实也不用merge interval，你只需要另外设置一个变量end记录上一个interval的边界，如果当前interval与之前的interval没有overlap，就输出[end, interval.start]到最终数组中。然后每次都得更新一下end。

这里只讲思路不写代码。代码还是自己写的才能理解深刻啊：）

遇到区间开头标记1，遇到结尾标记-1，然后从小到大扫一次，求和，把和0的区间就是答案。 最后在注意下开区间闭区间就行了

justin 发表于 2017-2-21 13:18
这题分两块：

1. merge k sorted array

根据您的想法，大概思路就是1. 用一个MinHeap,然后把start最小的interval Pop出来 2.然后用Math.Max来不断定义[lastInterval.end,currInterval.start]吗？

newgod2500 发表于 2017-2-21 01:16
根据您的想法，大概思路就是1. 用一个MinHeap,然后把start最小的interval Pop出来 2.然后用Math.Max来不 ...

我不知道Math.Max是啥。。。总之就是但凡发现前后两个interval不overlap，就输出这个区间。因为start都是升序的，所以这种greedy方式是可行的。

clfhaha1234 发表于 2017-2-21 14:13
遇到区间开头标记1，遇到结尾标记-1，然后从小到大扫一次，求和，把和0的区间就是答案。 最后在注意下开区 ...

我看“http://www.1point3acres.com/bbs/ ... &authorid=99793” 这贴也是大概这样做的..奈何看不懂Python...而且挺难理解，所以就只好来问问 。这个的确比用heap然后greedy的code会更加短小，谢谢你的点拨。