Interval这个概念在算法题中时有出现。这个概念理解起来很容易，就是一个区间(start, end)。可是这类题目做起来，却往往不那么简单。今天我来和大家分享一下，我心中对付interval类型的题目，所需要的三板斧。然后我会用我见到的9道和interval有关的题目，来演示这三板斧的使用。
第一，排序。在一般情况下，按照interval的start升序排序，在必要情况下，对于start相同的interval，按照interval的end的降序排序。
第二，greedy。有时候是两个interval之间的greedy，有时候是一群interval之间的greedy。
第三，map。c++里的map，是用红黑树实现的，这里为了方便就叫map。当前两板斧都无法奏效的时候，可以试试这个。
下面，我来演示一下，如何用这三板斧解决问题。
先来看第一板斧，排序。
最简单的例子，莫过于Leetcode 252 meeting rooms。
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. For example, Given [[0, 30],[5, 10],[15, 20]], return false.
这道题莫过于先按照start排序，然后检查每两个相邻的interval，看看前一个的end是否大于后一个start。实际上，一个没有任何编程经验的人也知道，想要看一个人能否出席所有的会议，那么就要看前一个会议结束的时候，下一个会议有没有开始。代码太简单就不放了。
下面一个例子稍微有点复杂，但是也是通过排序来解决的。这道contained interval来自csacademy.com, 题目废话太多我就不放了，感兴趣可以自己点进去。简单来说，给一组interval，判断有多少个interval是被至少一个别的interval所包含的(包含的定义：a包含b，就是 a.start <= b.start, a.end >= b.end)。
这道题的思路就是，先按照Interval的start升序排序，对于start相同的interval，按照interval的end的降序排序。这样子可以保证在排序后，对于每一个interval，如果它被另一个interval所包含，那么那个包含它的interval一定在它之前。这是排序的结果所造成的。同时因为排序，每一个interval的start一定大于等于之前的所有interval，所以只要之前有任意一个interval的end大于等于这个interval的end，那么就满足了包含的条件。于是我们就只需要在遍历排序过后的数组时，记录下出现过的最大的end，然后和当下的interval的end作比较。唯一需要注意的一点是，如果前后两个interval的start和end完全相等，那么意味着这两个interval同时被对方所包含，在这种情况下，我们不能漏算前一个interval的情况。因此我们每次都还要比较一下每个interval和后一个interval是否相等。来看一下我的代码，值得解释的是，因为对于排序过后的第一个元素，currentmaxR的比较条件必然成立，所以在初始化res的时候要考虑是否初始化成-1来抵消这次误加。
Read full article from 刷题笔记8（对付Interval的三板斧） - 知乎
No comments:
Post a Comment