d******a
发帖数: 238 | 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****t
发帖数: 69 | 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********u
发帖数: 1061 | 3 是不是相交，包括都算intersect？
我的想法是：排序加扫一遍就行了
根据interval的开头排序，
然后扫一遍，从第一个开始，每个interval的结尾从本interval的开头开始二分查找，
看超过了哪些interval的开头，超过的那个就互为intersect，两个interval的
intersect数目加1
扫完了找到最大的那个，就行了 | d******a
发帖数: 238 | 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******a
发帖数: 238 | 5 不是很明白？您能说的更详细点吗？谢谢！
【在 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******a
发帖数: 238 | 6 这个复杂度是 N * N? 你可能每次都超过k个interval的头，而且k不是O(1).
【在 x********u 的大作中提到】
: 是不是相交，包括都算intersect？
: 我的想法是：排序加扫一遍就行了
: 根据interval的开头排序，
: 然后扫一遍，从第一个开始，每个interval的结尾从本interval的开头开始二分查找，
: 看超过了哪些interval的开头，超过的那个就互为intersect，两个interval的
: intersect数目加1
: 扫完了找到最大的那个，就行了
| h****t
发帖数: 69 | 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****w
发帖数: 4 | 8 我的思路
1. 按si排序整个区间。
2. 去除被包含的子区间，记录包含区间中含有子区间的个数。
3. 顺序扫描区间，用小堆维护之前出现的fj，如果堆顶元素小于si,则弹出，剩下的元
素是相交元素的个数 & si > sj.
4. 逆序扫描区间，用大堆维护之前出现的sj，同理得到相交的区间个数 & sj < si。
5. 把步骤2, 3, 4得到的结果相加，就是该区间的相交区间个数。 | d*******s
发帖数: 695 | 9 这个似乎不行，但二分也许是个好思路
假设有个(6, 15) (7, 14) (7.5, 12） (8, 13)
对(7.5, 12)来说，一二分，就会把(6,15)给漏掉。
【在 x********u 的大作中提到】
: 是不是相交，包括都算intersect？
: 我的想法是：排序加扫一遍就行了
: 根据interval的开头排序，
: 然后扫一遍，从第一个开始，每个interval的结尾从本interval的开头开始二分查找，
: 看超过了哪些interval的开头，超过的那个就互为intersect，两个interval的
: intersect数目加1
: 扫完了找到最大的那个，就行了
| d*******s
发帖数: 695 | 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********u
发帖数: 1061 | 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***z
发帖数: 29 | 12 ls说的是对的，其实不难，画个图就行了。主要是如何算start在ai前，end在ai后的
interval。
分别按start，end点排序，对于每个interval，用bi点前start的数量-ai点前end的数
量就行了，2次binary search。 | m*****k
发帖数: 731 | 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*******9
发帖数: 138 | | m*****n
发帖数: 2152 | 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的方法不一样啊。
: 大家有什么好办法没？
|
|
