一道面试题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道面试题。

一道面试题。# JobHunting - 待字闺中

d*a2015-02-01 08:02

1 楼

giving lots of intervals [ai, bi], find the interval which intersect with
the most number of intervals n*logn 解法.
这个和Given n intervals [si, fi], find the maximum number of overlapping
intervals 那个 +1, -1的方法不一样啊。
大家有什么好办法没？

h*t2015-02-01 08:02

2 楼

Idea:
1) Sort the set of points ai, bi
2) Initialize start = 0, end = 0, Ni = 0
3) Iterate through sorted points
i) Encounter ai: start++, Ni = -end
ii) Encounter bi: end++, Ni += start - 1
4) Find biggest Ni

x*u2015-02-01 08:02

3 楼

是不是相交，包括都算intersect？
我的想法是：排序加扫一遍就行了
根据interval的开头排序，
然后扫一遍，从第一个开始，每个interval的结尾从本interval的开头开始二分查找，
看超过了哪些interval的开头，超过的那个就互为intersect，两个interval的
intersect数目加1
扫完了找到最大的那个，就行了

d*a2015-02-01 08:02

4 楼

不是很明白？您能说的更详细点吗？谢谢！

【在 h****t 的大作中提到】

: Idea:
: 1) Sort the set of points ai, bi
: 2) Initialize start = 0, end = 0, Ni = 0
: 3) Iterate through sorted points
: i) Encounter ai: start++, Ni = -end
: ii) Encounter bi: end++, Ni += start - 1
: 4) Find biggest Ni

d*a2015-02-01 08:02

5 楼

不是很明白？您能说的更详细点吗？谢谢！

【在 h****t 的大作中提到】

d*a2015-02-01 08:02

6 楼

这个复杂度是 N * N? 你可能每次都超过k个interval的头，而且k不是O(1).

【在 x********u 的大作中提到】

: 是不是相交，包括都算intersect？
: 我的想法是：排序加扫一遍就行了
: 根据interval的开头排序，
: 然后扫一遍，从第一个开始，每个interval的结尾从本interval的开头开始二分查找，
: 看超过了哪些interval的开头，超过的那个就互为intersect，两个interval的
: intersect数目加1
: 扫完了找到最大的那个，就行了

h*t2015-02-01 08:02

7 楼

Number of intervals intersected by interval i
= number of intervals with start point before ai and end point after ai
+ number of intervals with start point between ai and bi
= number of intervals with start point before bi (excluding ai)
- number of intervals with end point before ai
When you encounter ai,
end = Number of intervals with end point before ai
=> Ni = - end
When you encounter bi,
start = Number of intervals with start point before bi (ai included)
=> Ni += start - 1

【在 d******a 的大作中提到】

: 不是很明白？您能说的更详细点吗？谢谢！

u*w2015-02-01 08:02

8 楼

我的思路
1. 按si排序整个区间。
2. 去除被包含的子区间，记录包含区间中含有子区间的个数。
3. 顺序扫描区间，用小堆维护之前出现的fj，如果堆顶元素小于si,则弹出，剩下的元
素是相交元素的个数 & si > sj.
4. 逆序扫描区间，用大堆维护之前出现的sj，同理得到相交的区间个数 & sj < si。
5. 把步骤2, 3, 4得到的结果相加，就是该区间的相交区间个数。

d*s2015-02-01 08:02

9 楼

这个似乎不行，但二分也许是个好思路
假设有个(6, 15) (7, 14) (7.5, 12） (8, 13)
对(7.5, 12)来说，一二分，就会把(6,15)给漏掉。

【在 x********u 的大作中提到】

d*s2015-02-01 08:02

10 楼

好像是对的，但是还是不太难看懂，能写个例子么？多谢！

【在 h****t 的大作中提到】

: Number of intervals intersected by interval i
: = number of intervals with start point before ai and end point after ai
: + number of intervals with start point between ai and bi
: = number of intervals with start point before bi (excluding ai)
: - number of intervals with end point before ai
: When you encounter ai,
: end = Number of intervals with end point before ai
: => Ni = - end
: When you encounter bi,
: start = Number of intervals with start point before bi (ai included)

x*u2015-02-01 08:02

11 楼

哦，我搞错了，
我觉得可以有两个已经排序的数组对吧，一个存已经扫过的interval的end，这个数组
是动态更新的，每扫过一个就把本次interval的end写进去，数组是已排序的，写一个
新数字需要耗费logN
一个存还未扫过的interval的beginning，这样每扫到一个interval做两个二分查找么
，先查这个头越过了多少个之前interval的尾巴，耗费logN，再查这个尾巴越过了多少
之后interval的头，耗费logN，加法一次，就是这个interval和多少其他interval相交
了，你看这个对不对

【在 d******a 的大作中提到】

: 这个复杂度是 N * N? 你可能每次都超过k个interval的头，而且k不是O(1).

n*z2015-02-01 08:02

12 楼

ls说的是对的，其实不难，画个图就行了。主要是如何算start在ai前，end在ai后的
interval。
分别按start，end点排序，对于每个interval，用bi点前start的数量-ai点前end的数
量就行了，2次binary search。

m*k2015-02-01 08:02

13 楼

一道店面
public class RatePeriod {
private Date startDate;
private Date endDate;
private Integer nightlyRate;
/* Assume getters, setters, hashCode, equals, toString have been impl’d
. */
}
/**
Returns a flattened list of rate periods where “flattened” means that any
overlaps have been resolved by favoring the greatest nightlyRate for the
duration of the overlap.
Example:
flatten [(2015-01-01, 2015-12-31, 125), (2015-03-07, 2015-03-21, 175)]
Output:
[(2015-01-01, 2015-03-06, 125),
(2015-03-07, 2015-03-21, 175),
(2015-03-22, 2015-12-31, 125)]
Viz:
Jan 1 |------------------------------125------------------------------| Dec
31
Mar 07 |----175----| Mar 21
Output:
Jan 1 |-----125-----|----175----|----------------125------------------| Dec
31
dates may duplicate and there may be gaps as well.

x*92015-02-01 08:02

14 楼

先离散化一下，性能会好不少。

m*n2015-02-01 08:02

15 楼

题目没看懂，什么意思？
[1,4] [2,5] ： return [1, 4] or [2, 5] or None or all of them？
[1,4] [1,4] [2,5]: return [1, 4] or [2, 5] or None or all of them?
[1,4] [2,5] [1,5]: return [1,4] or [2, 5] or [1, 5] or all of them?

【在 d******a 的大作中提到】

: giving lots of intervals [ai, bi], find the interval which intersect with
: the most number of intervals n*logn 解法.
: 这个和Given n intervals [si, fi], find the maximum number of overlapping
: intervals 那个 +1, -1的方法不一样啊。
: 大家有什么好办法没？