OA

今天OA碰到一道题,由于时间不够没做出来,但是回头来看还是不难的,题目基本已经告诉你要用mono increasing stack 了。而且之前你也练习过模版,实际上套用一下就好了。时间不够还是因为你之前浪费了太多时间,包括第一道题。有时候通过简单的计数就可以解决的问题被你想复杂了。
不过有一道题类型是我没见过的,university career fair这道题属于interval scheduling,meeting room应该算是同类型的吧?但是自己还是没能马上做出来。我觉得还是熟练度不够。但看过Wikipedia之后发现这种问题有统一的算法解,就直接套用greedy就可以了。也算是学到东西了。就是按照每个meeting结束时间来排序,然后算最大或者你想要的结果。
第一步,把最早结束的meeting取出来,然后把有overlap时间的meeting全部剔除,再往后计算结果就可以得到最佳答案。原文如下

The following greedy algorithm does find the optimal solution:

  1. Select the interval, x, with the earliest finishing time.
  2. Remove x, and all intervals intersecting x, from the set of candidate intervals.
  3. Repeat until the set of candidate intervals is empty.

建图是一个很重要的步骤,要学会如何建图,参考城主的视频我觉得可以,里面建图方式如何实现都可以学习一下,然后再练习如何实现这个算法。先把图论里面所有算法都熟练掌握才可以。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容