扫描线?数飞机 (Interval overlap)

From 九章算法


这题可以理解为给定的interval里,最大overlapping数量。


这个想法太赞了,完全不需要sort interval。 创造一个object class, start的时间和end的时间都可以用来当做时间这个time variable 放在class里。

然后 sort a list of Objects based on time variable.   start1---start2---end1---end2...

然后iterate。当看到start的时候 count++. 看到end的时候 count--. 然后取max count 就好了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容