O******i
发帖数: 269 | 1 我要是当时看过题目二就好了，哎...
题目一，我的面经，出处
http://www.mitbbs.com/article_t/JobHunting/32010769.html
有一个类，里头有两个Date对象
class T
{
Date date1;
Date date2;
}
其中Date是形如12/05/2011这样的日期，date1 <= date2，这样T就表示一个时间段。
假如有两个T类型的变量a,b，如果a和b代表的时间段之间没有gap, 也就是a和b
overlap, 则集合{a, b}是连续的。然后他解释扩展到多个时间段，什么情况下他们的
集合是连续的。
他的问题是，给你一个T类型变量的list，如何判断这个list是连续的还是不连续的。
我很快发现，每个Date在时间轴上是一个点，每个时间段T的变量是时间轴上的一条线
段，这题完全可以等同于
class Seg
{
int start;
int end;
}
其中 start <= end, 这样Seg就表示数轴上的线段。两条线段如果overlap，包括
overlap于一个点，则连续。他无非想用时间这个概念来使得问题看起来更复杂些。
排序后，如果第一条线段和第二条线段不连续，则整个list不连续，可以返回false，
如果连续，则merge这两条线段，然后再考察merge后的线段和第三条线段，最后或者遍
历完所有的线段，或者中途就返回false。
题目二，传说中G的面经，出处
http://www.mitbbs.com/article_t/JobHunting/32079031.html
http://www.mitbbs.com/article_t/JobHunting/31997875.html
Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the
intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their
start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[
3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]. | p*****2
发帖数: 21240 | | O******i
发帖数: 269 | 3 第一题要是没想到要先用排序作预处理，就会像我那样悲剧了。
【在 p*****2 的大作中提到】
: 第一题应该比第二题容易吧。
| p*****2
发帖数: 21240 | 4
其实我碰到这种题经常偷懒。建立一个数组，从最早的时间到最晚的时间，一个元素代
表一天。
然后扫一遍intervals去填数组。最后检查数组是不是完全被访问过。
【在 O******i 的大作中提到】
: 第一题要是没想到要先用排序作预处理，就会像我那样悲剧了。
|
|
