注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(64)-日程安排表[算法]  

2018-01-04 07:45:26|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目:请实现一个类型My Calendar用来记录你的日程安排,该类型有一个方法book(int start, int end)往日程安排表里添加一个时间区域为[start, end)的事项(这是个半开半闭区间,即start<=x<end)。如果[start, end)内没有事先安排其他事项,则成功添加该事项并返回true。否则不能添加该事项,并返回false。假设输入的start和end都在区间[0, 10^9]之内。

例如,在下面的三次调用book方法中,第二次调用返回false,这是因为时间[15, 20)已经被第一次调用预留了。由于第一次占用的时间是个半开半闭区间,并没有真正占用时间20,因此不影响第三次调用预留时间区间[20, 30)。

MyCalendar cal = new MyCalendar();

cal.book(10, 20); // returns true

cal.book(15, 25); // returns false

cal.book(20, 30); // returns true


分析:这是LeetCode第729题。

解法一:基于TreeMap

每个添加到日程安排表里的事项都占用一个时间段。根据题目的要求,两个事项不能占用同一个时间段,也就是事项对应的时间区间不能重叠。当我们需要插入一个新的事项的时候,我们需要遍历日程安排表里已有事项占用的时间区间。

如果待添加的事项占用的时间区间是[m, n),我们需要找出开始时间小于m的所有事项里开始最晚的一个,以及开始时间大于m的所有事项里开始最早的一个。如果这两个事项都和该事项没有重叠,那么该事项可以添加到日常安排表中。

我们可以根据时间区间的开始时间进行排序,通常排序之后能够优化查找的效率。如果我们把这些排序的时间区间用链表存储,扫描一遍链表需要O(n)的时间。

由于需要在排序好的时间区间里搜索,一个直观的优化是把这些时间区间存储到搜索二叉树里。在二叉搜索树里进行查找、插入、删除操作的时间复杂度都是O(logn)。

如果面试官允许我们使用库里的二叉树的数据结构,那再好不过了。不同编程语言提供的二叉树实现不尽相同。

下面以Java为例。由于每个区间除了有开始时间,还有结束时间,也就是说树的每个节点需要保存两个数字。一个简单的办法是用TreeMap。在TreeMap中,每个节点是一个映射,我们可以把时间区间的开始时间作为映射的键值,把结束时间作为映射的值。

基于Java中的TreeMap的实现如下:

程序员面试题精选100题(64)-日程安排表[算法] - 何海涛 - 微软、Google等面试题

 

在上述代码的book方法调用了TreeMap的成员方法floorEntry。该方法能够找出二叉树中所有开始时间比时间start早的所有事项中开始时间最大的事项。如果该事项的在start之后结束,则与待添加的事项重叠,返回false。

book方法还调用了TreeMap的成员方法ceilingEntry。该方法能够在二叉树中所有开始时间比时间start晚的所有事项中开始时间最小的事项。如果该事项的在end之前开始,则与待添加的事项重叠,返回false。

如果上面两次找出的两个事项都不和待添加的事项重叠,那么就可以把事项添加到日程安排表,并返回true。

TreeMap能够保证在树中查找、添加和删除的时间复杂度都是O(logn)。


解法二:自己实现二叉搜索树

有些时侯面试官为了增加面试的难度,会故意限制使用库里的类型和方法。如果是这样,我们不得不自己实现二叉搜索树。要完整实现二叉搜索树的添加节点比较麻烦,在面试有限的时间里不一定来得及。好在我们有更加简便的办法。

我们换个思路来看这个问题。假设我们准备添加一个时间区间为[m, n)的事项。如果我们能够找到一个空闲的时间区间[i, j)并且满足m>=i和n<=j,那么说明时间区域[m,n)没有被其他事项占用,可以添加该事项。添加这个事项之后,我们需要把时间区间[i, j)从空闲时间里删除,并添加两个空闲时间区间[i, m)和[j, n)。

我们可以想象,在若干次成功在日程安排表上添加事项后,空闲时间被切割成若干段相互不重叠的空闲时间区间。在试图添加新的事项的时候,我们需要快速从这些时间区间中找出一个合适的时间区间,该区间的起始时间小于或等于事项开始的时间,同时该区间结束的时间大于或者等于事项结束的时间。

当一个事项把一个空闲时间区间切分成两个区间时,我们并不把原来的空闲时间区间删除,只是把新的两个时间区间作为原来区间的左、右子节点添加到二叉树中。如果原来的时间区间为[i, j),在添加时间区间为[m, n)的事项之后,我们为时间区间[i, j)对应的节点添加左子节点[i, m)和[n, j)。

用这种方法添加节点之后,只有叶子节点才是真正的空闲时间区间。当我们为时间区间[m, n)的事项搜索空闲时间区间时,从跟节点开始,如果m小于左子节点的结束时间,则下一步到它的左子树里搜索;如果m大于右子节点的开始时间,则下一步到它的右子树里搜索。这样一直搜索到一个叶子节点[i, j)满足i<=m并且j>=n,则可以添加当前事项。

基于这个思路,我们可以定义二叉树中的节点(即空闲时间区间)如下:

程序员面试题精选100题(64)-日程安排表[算法] - 何海涛 - 微软、Google等面试题

每个节点都包含时间区间的开始时间和结束时间,同时它还包含左、右子节点的引用。

接下来是实现book操作的代码:

程序员面试题精选100题(64)-日程安排表[算法] - 何海涛 - 微软、Google等面试题

由于我们是在二叉搜索树上做查找,因此每次book的时间复杂度也是O(logn)。由于这里添加节点的时间复杂度为O(1),因此总的时间效率要优于第一种解法。该解法比90%的LeetCode中Java代码提交的执行时间效率要高。

当然我们并不能保证生成的二叉搜索树一定的平衡的,理论上二叉树的高度可能是O(n),因此查找的时间复杂度可能会退化到O(n)。

该方法不依赖于任何库里的类型和方法,翻译成其他编程语言非常容易。如果我们在面试的时候一时想不起来库里已有的类型,或者我们熟悉的编程语言的库里没有类似于TreeMap的数据结构(比如C、Python的标准库里都没有),那么不妨使用第二种解法,尽管代码的行数可能稍微多一些。

本文转载自微信公众号“青云算法”。扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(64)-日程安排表[算法] - 何海涛 - 微软、Google等面试题
 
  评论这张
 
阅读(301)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018