一个模板刷N题-treeMap解区间题

diamondsky 发表于 2020-1-22 13:15
非常棒！

> 56 merge intervals 如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理 ...

代码中intervals的索引都少了一个维度，应该是intervals[i][0]/intervals[i][1]，可能是打的时候漏掉了？

scope 发表于 2020/01/21 23:53:22
为什么不用HashMap用TreeMap呢？

是的 这个没必要用treemap 速度上会有损失

楼主很谦虚。楼主代码质量还是很不错的，手练熟一点，有横扫的潜力。

这个解法我一般称呼为扫描时间线，的确是一个非常好的算法，我也在面试中使用过3次，都通过了，说明认可度还是很高的。
但是其实这个算法的本质我觉得应该是侧重于堆的使用上，至于选择用treemap还是python里自己实现heap都是可以的，一般面试的时候提到heap，面试官会基本默认你已经过了这个题了。
这类题的集大成者是这个hard：218. The Skyline Problem，我觉得把这个掌握了，这一类问题就差不多了。

谢谢楼主，来学习一下

vivflynn 发表于 2020-1-25 23:13
是的 这个没必要用treemap 速度上会有损失

我不太清楚你这里说的"这个"具体是指什么。

如果是使用楼主本帖描述的扫描线(Sweep Line)算法，那TreeMap几乎是是必须的。如果不是必须的，我个人也是强烈推荐的。
横轴(x轴/时间轴)上的坐标(即TreeMap的Keys)需要严格排序。排序规则往往是时间线、x轴坐标等，这个看具体题目，这也是这个算法起名的由来。
横轴上坐标对应了纵轴的值，怎么排序横轴会影响纵轴的值的分布，自然会影响到扫描(Sweep)的过程，也就会影响到最后的答案。
Java - Priority Queue也能达到排序的效果。但，相比较TreeMap而言，删除keys的时候，是个O(PQ_SIZE)的操作。

HashMap的Keys之间是无序的。除非能确保HashMap能达到以上(扫描线排序的)效果，就可以使用HashMap。
同时，有时候keys无序的时候，得出的答案可能也是正确的，但扫描过程很有可能是不一样的。
即便是这样，我也强烈建议不要使用HashMap。

一家之言，请多多指教。

这是我总结的可以使用扫描线算法的题目列表 - github

在使用扫描线算法时，留心两个时刻：
一个是最开始扫描的时候，表现在纵轴由0变成有值。
一个是中间纵轴由有值变成0(甚至负值)的时候。
616. Add Bold Tag in String
758. Bold Words in String

   很有用的信息！很有用的信息！

zea7ot 发表于 2020-08-24 18:10:35
我不太清楚你这里说的"这个"具体是指什么。

如果是使用楼主本帖描述的扫描线(Sweep Line)算法，那TreeMap几乎是是必须的。如果不是必须的，我个人也是强烈推荐的。

嗯嗯 我觉得你对扫描线算法的理解是对的 但是就对这两题而言 我们扫描过程不是由这个map决定的而是由那个for 循环 你看代码只有读值和插入对吧 其实这题的本质就是start 和 end 的频率统计 所以其实不需要treemap

Python可以看情况选用OrderedDict, 但这个API的效果见仁见智吧，看别人discuss里经常用，我没用过

堆确实也是个好方法，这个我常用，毕竟线段树让我现场python实现，我宁愿花时间多看看system design

戳气球那道题不能这样做