r**d
发帖数: 90 | 1 2 5 7 13 17 18
------------------- ------------------------ ----
------------
2 13 17 18
------------------------------------------------ ----
------------------- ------------------------ ----
-----------------------------------------------------------
-------------------------------------------------------------
struct Interval {
float min;
float max;
}
vector mergeIntervals(const vector& list, const Interval
newInterval) {
Vector intervals = new Vector
给定 a list of intervals, 然后输入一个interval.
then merge the interal list
for example, interval (2, 6) (8, 10), input (4,20)
output will be (2, 20) |
h*******e
发帖数: 1377 | |
g****y
发帖数: 240 | 3 binary search?
【在 r**d 的大作中提到】
: 2 5 7 13 17 18
: ------------------- ------------------------ ----
: ------------
: 2 13 17 18
: ------------------------------------------------ ----
: ------------------- ------------------------ ----
: -----------------------------------------------------------
: -------------------------------------------------------------
: struct Interval {
: float min;
|
l*****a
发帖数: 14598 | 4 就一道？电话？
【在 r**d 的大作中提到】
: 2 5 7 13 17 18
: ------------------- ------------------------ ----
: ------------
: 2 13 17 18
: ------------------------------------------------ ----
: ------------------- ------------------------ ----
: -----------------------------------------------------------
: -------------------------------------------------------------
: struct Interval {
: float min;
|
r**d
发帖数: 90 | 5 应该不是
要求O(n)time
【在 g****y 的大作中提到】
: binary search?
|
f*******t
发帖数: 7549 | |
p*****2
发帖数: 21240 | |
r**d
发帖数: 90 | 8 电面，两题，见（2）
【在 l*****a 的大作中提到】
: 就一道？电话？
|
l***m
发帖数: 339 | 9 我觉得这题就扫一遍就好，没有什么花哨的算法。
【在 r**d 的大作中提到】
: 应该不是
: 要求O(n)time
|
r****i
发帖数: 528 | |
|
|
d******i
发帖数: 76 | |
e***s
发帖数: 799 | |
t*********7
发帖数: 255 | 13 前提是那个INTERVALS要是排序的吧... |
m*d
发帖数: 7658 | 14 电面考这个是不是难了点
【在 r**d 的大作中提到】
: 2 5 7 13 17 18
: ------------------- ------------------------ ----
: ------------
: 2 13 17 18
: ------------------------------------------------ ----
: ------------------- ------------------------ ----
: -----------------------------------------------------------
: -------------------------------------------------------------
: struct Interval {
: float min;
|
h*******l
发帖数: 22 | 15 对静态interval set：（leetcode上的）
排序，nlgn
过一遍， n
动态的（不停有interval 插入）
方法一：
每个新的都插入到正确的位置，lgn
再过一遍，n
结果是n^2 的
方法2：
2.1 假设知道所有end points，比如1--1000000，每个点都是可能的endpoints
根据end point 建segment tree
每个新的插入需要lgn
总共nlgn
2.2 不知道end points
完全动态的segment tree，每次插入需要rebalance （O(1)）
修改union lgn
插入endpoints lgn
总共nlgn
这个就比较复杂了， 感觉面试仅停留于静态的就不错了
|
