基础算法(一) -- 扫描线

[@eddiedu3725]

0:00 扫描线基础算法 1:34 LintCode 391 5:20 LC 252 必掌握 7:31 LC 253 非常经典 9:30 LC 253 PQ解法 15:29 LC 56 intervals 三兄弟 29:45 LC 435 42:10 LC 1229 返回最早的common slot 44:27 LC 986 返回所有common working time 45:56 LC 759 48:06 LC 218 The Skyline Problem 1:00:59 Summary

[@eddiedu3725]

0:00 扫描线基础算法 1:34 LintCode 391 5:20 LC 252 Meeting Rooms 必掌握 7:31 LC 253 Meeting Rooms II 非常经典 9:30 LC 253 Meeting Rooms II PQ解法 15:29 LC 56,57, 1272 intervals 三兄弟 - Merge Interval, Insert Interval, Remove Interval 29:45 LC 435 Non-overlapping Intervals 42:10 LC 1229 Meeting Scheduler 返回最早的common slot 44:27 LC 986. Interval List Intersections 返回所有common working time 45:56 LC 759 Employee Free Time 48:06 LC 218 The Skyline Problem 1:00:59 Summary

[@joymu6539]

画图太直观了！一下子把情况讨论清楚了 谢谢群主！

[@Grace0720mcy]

1:34 LintCode 391 5:20 LC 252 必掌握 7:31 LC 253 非常经典 9:30 LC 253 PQ解法 15:29 LC 56 intervals 三兄弟 29:45 LC 435 42:10 LC 1229 返回最早的common slot 44:27 LC 986 返回所有common working time 45:56 LC 759 48:06 LC 218 The Skyline Problem

[@xihongshi414]

最后一道skyline题号218

[@Grace0720mcy]

@@xihongshi414 谢谢，我更新了

[@dr_920]

352第一反应想到的是union find，做起来也挺方便的。感觉跟着古城刷了一段时间，有点开窍了。

[@SmallV168]

非常好，有点小建议，sort时最好return Integer.compare(b, a)或者有自带的Comparable方法的话 return Integer.compare(a, b)，避免overflow问题

[@古城算法]

是的呢，说的很对。平时contest习惯了写的快，面试可以comparator使用考虑了边界条件的Integer.compare

[@SmallV168]

@@古城算法 很牛啊，还参加contest，我加了群，但是没反应，我感觉咱俩性格很像应该比较聊得来，我也非常喜欢分享，应该加个微信

[@古城算法]

@@SmallV168 群已经加啦~

[@古城算法]

@@SmallV168 哈哈没有啦，只是lc本身的contest，还有很多很多其他算法比赛我是没有碰的

[@VolatilityEdgeRunner]

leetcode 352做复杂了，不用treeset，就是建立一个interval [value, value] 然后调用merge interval就好了。只不过当end point + 1 < cur_start 或者cur_end + 1 < start_point不merge。

[@jianhuahe4066]

at 53:30, line 20, there is a bug - if pq is empty, curMax = 0 else curMax = pq.peek()

[@LongweiSu]

line 15, pq 初始化了个0，所以无论怎样都不会为空

[@libbyy5608]

古老师，在讲解435这道题（P20）的时候，应该是 “If conflict always remove current one, to leave more space for the later. ”？因为intervals按照结束时间排序，previous的结束时间应该是小于等于current的结束时间的，有冲突的时候remove current interval才会释放更多的time。代码里也是，当遇到conflict的时候，end的时间是不更改的。

[@古城算法]

说的对！！

[@charlesliu1439]

讲得真好

[@maxwang9346]

其实依然可以强行用heap来实现 logn 删除。heap虽然只能删除第一个没有错，但是我们可以等到后面再删除它，当前只要max不变，就谁也不删除。每次max变了就一直heappop 多heappop几个已经结束的building 从而继续拿到当前Max。

[@古城算法]

请问有代码嘛，我来学习一下

[@dragonzhao433]

@@古城算法 public List getSkyline(int[][] buildings) { List res = new ArrayList(); List height = new ArrayList(); for(int[] b:buildings) { height.add(new int[]{b[0], -b[2], b[1]}); height.add(new int[]{b[1], b[2]}); } Collections.sort(height, (a, b) -> a[0] == b[0]?a[1]-b[1]:a[0] -b[0]); PriorityQueue pq = new PriorityQueue((a,b)->(b.get(0)-a.get(0))); int preMax = 0; int index = 0; for(int[] h: height) { if(h[1] < 0) { pq.offer(Arrays.asList(-h[1], h[2])); } else { while(!pq.isEmpty() && pq.peek().get(1)

[@jinhuizhang702]

非常棒！ 支持！

[@joymu6539]

42:00 Data Stream as Disjoint Intervals用 set.contains(interval)判断区间是否存在是不是永远都是 false？new 的数组和原来的不 identical

[@古城算法]

我重写了treeSet的comparator在第2行 TreeSet set = new TreeSet((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

[@wanda6461]

@@古城算法 重写compartor对set判断是不是contains应该没有影响吧 都是调用equals判断的 也就是int[]的地址 一般不把array加到set或者map里 可以加list

[@zenzen4397]

小猪那题笑我了

[@whyrutryingsohard]

天際線問題似乎在Python的heaps中沒有提供remove API, 需要利用類似單調棧的方式pop出小於目前新房子的方式

[@willshen5051]

直接当作list remove， 再重新 heapify 就好。

[@meiqihe3708]

太感谢了！讲的真好

[@jimmycheng709]

The best ever!

[@古城算法]

thanks a lot!

[@j.franciscox3318]

请教一下 Interval[]是什么数据结构？

[@kkbox1125]

Great contents!! Thanks for sharing!!

[@古城算法]

Thanks for your support!

[@eaglezhou1243]

哈哈，多人运动。 谢谢古城，这个视频做的太给力了。

[@古城算法]

哈哈哈哈，谢谢支持！

[@EdwardWang]

Skyline离散化一下然后用线段树，其实只需要实现将一个区间变成某个值的操作，线段树懒标记可以log n做。最后dfs一遍。其实就是个板子题🥹🥹🥹

[@codemonkey2614]

没搞懂15:17的地方，前面10个meeting, 9个meeting的开始时间都早于第1个meeting的结束时间，那么room++就变成了10，也就是说需要10个房间才能开这10个meeting。现在第11个meeting, 的开始时间晚于所有前面10个meeting的结束时间，那么现在只有第11个meeting在，前面meeting都结束了。 假设，又来了10个meeting, 他们的开始时间都晚于第11个meeting的结束时间，那么room有累加10？那不最后不成了room是20了？但实际只需要10个room啊。前面会议结束，不需要room-- ？

[@古城算法]

因为第11个meeting的时候end到了第二个meeting的end，然后room不加。 第12个meeting同样，都是end只加一次。 这个思路的核心在于动态保存窗口最大meeting，有新的meeting来就把旧的meeting踢出去(如果旧的meeting已经可以结束的话，而且这个时候window最大值没有更新) 如果还是不太理解的话，建议面试还是直接用数飞机思路更直接

[@skyzjkang]

赞，讲的真不错。我感觉我大概写了差不多1000题，但是没有真正总结

[@古城算法]

加油加油，一起学习进步！

[@ronzhang6510]

collections.sort 那个函数其实不是很清楚 ：（

[@ZhaoqiWang-v1u]

牛逼 感谢

[@sinco1042]

1229那道是否可以直接数飞机，两架的时候记录start，降落一架的时候计算距离start是否满足duration

[@xiaohan3629]

可以 我就是这么做的

[@diaoyuanhuzhenhuiqi]

为什么要把左边界设成负数，右边界为正。如果左边为正，右边为负不是更方便吗

[@古城算法]

请问你问的是第几题，视频时间点在？

[@ruige2865]

@@古城算法 应该是天际线那道题， 54:24， 每个building的左边设为正height，右边设为负height ，然后sort的时候当扫描线的位置相同的时候改为maxHeap 高度(a, b) -> (a[0] == b[0]) ? b[1] - a[1] : a[0] - b[0]); 我也不太明白为什么左边要为负，为正感觉更intuitive一些

[@古城算法]

@@ruige2865 因为我们和数飞机一样，要让同一个时间的飞机先降落，后起飞。因为天际线是保留后置位的高度，所以同一个x坐标，有房子倒塌，有新房子起来，我们要的是后置位的新房子，也就是负数倒塌在前，正数新房在后

[@diaoyuanhuzhenhuiqi]

@@ruige2865 嗯嗯是的，谢啦

[@diaoyuanhuzhenhuiqi]

@@古城算法 嗯嗯，明白啦，谢谢哥哥

[@frederickbarbarossa2746]

56:00 第十五行 为什么pq.offer(0)?

[@frederickbarbarossa2746]

自己来回答这个问题 是为了方便加入第一个keypoint

[@weiyao806]

就是为了看最后一题，看到LC上给的答案是分治法，没有特别明白，能不能给讲讲。另外，线段树有专题么？

[@古城算法]

divide conquer应该也可以，只是代码有点多。直接用扫描线代码只有26行。 docs.google.com/presentation/d/1ai907zOZSflW9rMmEA9JdjwPwlozxuhPq_q55XO4NHA/edit kzbin.info/www/bejne/ipOzpoiheryMaLs&ab_channel=%E5%8F%A4%E5%9F%8E%E7%AE%97%E6%B3%95

[@weiyao806]

52 分钟那个slide，不是房子起点的高度设为负数进队列么？为什么左边(x,y)那里是房子终点的高度为负值？

[@古城算法]

height sort根据起点在前，终点在后。楼的高度正负来判断是起点还是终点 pq用来排列影子的高度，只有最高的影子边界可以成为结果的一部分

[@dididudidirua_4596]

Hi，想请教下10:57 这里29行if那个判断，我们是合并了两个区间吗？ 还是说我们由于heap是根据结束时间排序，所以我们只关注更新结束时间，但是实际上是将整个curr都替换成了intervals[i]?

[@古城算法]

当两个meeting时间不冲突的时候，我们是可以合并其成为同一个的，因为不需要更多的meeting room

[@古城算法]

就直接用数飞机的方法挺好的，不太需要最后用heapsize的方法。

[@dididudidirua_4596]

@@古城算法 好的谢谢

[@dididudidirua_4596]

@@古城算法 好的谢谢

[@hacksbsb]

罗志祥躺枪

[@古城算法]

哈哈哈

[@yayayu2bee131]

lol Non-overlapping intervals 那个题目我放好板凳准备听的时候，发现头几分钟你自己也把自己绕进去了哈哈哈

[@古城算法]

hahahah, 早期课件水平还很浮动哈哈哈😁

[@yayayu2bee131]

@@古城算法 我这几周就是看你的备试，prefixsum以后还有关于算法或者数据结构的吗？我好提早复习一下 谢谢。

[@古城算法]

@@yayayu2bee131 7，8月我们会安排系统设计部分，9月后面试期我们再回到算法部分。

[@Observer-w6k]

晋人？

[@maggiez3792]

怎么加入周五的zoom讨论呀？求指路。

[@古城算法]

看这里 kzbin.info%E5%8F%A4%E5%9F%8E%E7%AE%97%E6%B3%95/about

[@tonygai9181]

就是需要这种干练的视频，留个号，打钱

[@古城算法]

哈哈哈，多谢老铁的火箭！