Google 电面

yangdaxian 发表于 2018-6-19 00:05
那您再试试{0,0,10,2},{3,3,4,4},{9,1,10,6}吧，应该是挡住了，但按照这个方法是没挡住...

大概知道问题在哪儿了，不过这样就很麻烦，一小时肯定写不出来，whatever加油

kan yin cang

这个类似吧吴玲，用线段树可以做到nlogn

感谢楼主分享

把左下角点先按照xsort一般，再按照ysort 一遍应该可以 nlogn

我觉得这个可以转化成利口skyline那题的变形。。。 用PriorityQueue给每个长方形排列根据x，然后吧左下和右上端点放进去，然后横着扫过去。。。 这样我们就可以得到合并后的group(新的merge过的图形)，然后再合并途中记录Ymin 和 Ymax 就能判断是否堵住路了。 但是我发现的问题在于，如果两个group相互平行 这样就没办法准确找出合并后的group了

感谢将分，还有十几分就可以看了哈哈