Redian新闻
>
区间合并题的两种变体?
avatar
区间合并题的两种变体?# JobHunting - 待字闺中
O*i
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].
avatar
p*2
2
第一题应该比第二题容易吧。
avatar
O*i
3
第一题要是没想到要先用排序作预处理,就会像我那样悲剧了。

【在 p*****2 的大作中提到】
: 第一题应该比第二题容易吧。
avatar
p*2
4

其实我碰到这种题经常偷懒。建立一个数组,从最早的时间到最晚的时间,一个元素代
表一天。
然后扫一遍intervals去填数组。最后检查数组是不是完全被访问过。

【在 O******i 的大作中提到】
: 第一题要是没想到要先用排序作预处理,就会像我那样悲剧了。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。