s********x
发帖数: 914 | 1 ls的binary search还是有可以improve的地方，因为在hit到某个interval时search就
可以停止了，效率更高。我贴一些我的代码吧。思路是跟ls一样的。谢谢ls的代码。
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
int n = intervals.size();
if (n==0) {
intervals.add(newInterval);
return intervals;
}
int first = -1, last = -1; // first and last interval to be merged/
erased
int l = 0, r = n - 1;
// BSearch to find the 'first' interval whose end >= ne... 阅读全帖 |
|
s********x
发帖数: 914 | 2 ls的binary search还是有可以improve的地方，因为在hit到某个interval时search就
可以停止了，效率更高。我贴一些我的代码吧。思路是跟ls一样的。谢谢ls的代码。
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
int n = intervals.size();
if (n==0) {
intervals.add(newInterval);
return intervals;
}
int first = -1, last = -1; // first and last interval to be merged/
erased
int l = 0, r = n - 1;
// BSearch to find the 'first' interval whose end >= ne... 阅读全帖 |
|
s*****y
发帖数: 897 | 3 code did not support stream interval yet
typedef pair Interval;
vector Merge(vector &Intervals)
{
vector joinIntervals(0);
if (Intervals.size() == 0)
return joinIntervals;
sort(Intervals.begin(), Intervals.end());
int left = Intervals[0].first;
int right = Intervals[0].second;
for (int i = 1; i < Intervals.size(); i++) {
if (Intervals[i].first <= right) {
right = max(right, Intervals[i].second);
}... 阅读全帖 |
|
y*****e
发帖数: 18 | 4 /*
Algorithm: Modified Binary search
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1. BSearch to find the 'first' interval whose end >= newInterval.start.
If does not find, the new interval should be appended at the tail.
2. BSearch to find the 'last' interval whose start <= newInterval.end.
If does not find, the new interval should be inserted before the head.
3. Erase the found 'first' to 'last' intervals and insert the new merged
interval at index 'first'
*/
vector i... 阅读全帖 |
|
y*****e
发帖数: 18 | 5 /*
Algorithm: Modified Binary search
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1. BSearch to find the 'first' interval whose end >= newInterval.start.
If does not find, the new interval should be appended at the tail.
2. BSearch to find the 'last' interval whose start <= newInterval.end.
If does not find, the new interval should be inserted before the head.
3. Erase the found 'first' to 'last' intervals and insert the new merged
interval at index 'first'
*/
vector i... 阅读全帖 |
|
i**********e
发帖数: 1145 | 6 写了一个 O(n) 的 in-place insert。
如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
，然后更改第一个overlap的区间。
如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
，然后insert。
如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
把区间push到最后边。
class Solution {
public:
vector intervals;
void insert(Interval newInterval) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
if (newInterval.end < intervals[i].start) {
moveRight(i, 1);
intervals[i] = newInterval;
return;
} else {
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 7 写了一个 O(n) 的 in-place insert。
如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
，然后更改第一个overlap的区间。
如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
，然后insert。
如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
把区间push到最后边。
class Solution {
public:
vector intervals;
void insert(Interval newInterval) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
if (newInterval.end < intervals[i].start) {
moveRight(i, 1);
intervals[i] = newInterval;
return;
} else {
... 阅读全帖 |
|
s*******y
发帖数: 44 | 8 我一开始也是这个思路，顺序遍历，找到左右overlap的interval，然后删除、插入。
查找过程可以用binary search优化到logn。
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, pos;
while (i < size && intervals[i].end < newInterval.start) i++; //
lef... 阅读全帖 |
|
s*******y
发帖数: 44 | 9 我一开始也是这个思路，顺序遍历，找到左右overlap的interval，然后删除、插入。
查找过程可以用binary search优化到logn。
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, pos;
while (i < size && intervals[i].end < newInterval.start) i++; //
lef... 阅读全帖 |
|
k*****y
发帖数: 744 | 10 用stl写个练练手。
struct cmp_start{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.start < rhs.start;
}
};
struct cmp_end{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.end < rhs.end;
}
};
vector insert(vector &intervals, Interval newInterval) {
vector::iterator lower, upper;
lower = lower_bound(intervals.begin(), intervals.end(),
Interval(newInterval.st... 阅读全帖 |
|
k*****y
发帖数: 744 | 11 用stl写个练练手。
struct cmp_start{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.start < rhs.start;
}
};
struct cmp_end{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.end < rhs.end;
}
};
vector insert(vector &intervals, Interval newInterval) {
vector::iterator lower, upper;
lower = lower_bound(intervals.begin(), intervals.end(),
Interval(newInterval.st... 阅读全帖 |
|
e******i
发帖数: 106 | 12 下面是我的代码。
我暂时还没有想好怎么优化,请各位大神不吝赐教！：）
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList result = new ArrayList();
... 阅读全帖 |
|
y******n
发帖数: 4527 | 13 最近总是很懒，long run跑的不长，middle long也跑的很少。幸亏这边有running
group，每周三周五都有活动，还可以保持一些quality workout。今天在track上面进
行8*400m的interval。风很大，大约有4-5级的样子，顶风的时候觉得怎么使劲都在
slow down。
split如下：400米的interval，200米的recovery，8组。跑之前热身2迈，之后cool
down 1.5迈。Workout done on a high school track.
Interval 0.26 mi 1:17.2
Interval 0.13 mi 1:35.98
Interval 0.26 mi 1:17
Interval 0.13 mi 1:35.57
Interval 0.26 mi 1:16.6
... 阅读全帖 |
|
b******t
发帖数: 965 | 14 写个C++的
bool myfunction(Interval a, Interval b) {
return (a.start < b.start);
}
class Solution {
public:
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
intervals.insert(lower_bound(intervals.begin(),intervals.end(),
newInterval,myfunction),newInterval);
vector result;
if(intervals.size()>0)
result.push_back(inter... 阅读全帖 |
|
b******t
发帖数: 965 | 15 写个C++的
bool myfunction(Interval a, Interval b) {
return (a.start < b.start);
}
class Solution {
public:
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
intervals.insert(lower_bound(intervals.begin(),intervals.end(),
newInterval,myfunction),newInterval);
vector result;
if(intervals.size()>0)
result.push_back(inter... 阅读全帖 |
|
w***n
发帖数: 9040 | 16 昨天我跑了芝马以前的最后一次interval 3个200m，3个800m
Interval WO9 = 3 x 200 @ 85-90% with 200 jog recovery / 400 jog / 3 x 800 @
85% with 400 jog recovery.
Type Distance Split settings Duration Total Duration Pace
Avg HR Max HR
1 Interval 0.15 mi 0:40.55 0:41.45 4:37 152 164 1
Interval 200m
2 Recovery 0.14 mi 1:30.40 2:11.85 10:46 152 167 1
Recovery 200m
3 Interval 0.14 mi 0:38.37 2:50.22 4:35 164 178 2
Interval 200m
4 ... 阅读全帖 |
|
h*****g
发帖数: 312 | 17 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include |
|
h*****g
发帖数: 312 | 18 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include |
|
h*****g
发帖数: 312 | 19 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include |
|
h*****g
发帖数: 312 | 20 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include |
|
w****g
发帖数: 3 | 21 我用的是先sort的解法。
http://www.yangsheep.net/wuyang/wordpress/?p=727
class Solution {
public:
struct mycmpclass {
bool operator() (Interval i,Interval j) { return (i.start < j.start); }
} mycmpobject;
vector merge(vector &intervals) {
vector ans;
if(intervals.empty()) return ans;
sort(intervals.begin(), intervals.end(), mycmpobject);
Interval cur=intervals[0];
for(int i = 1; i < intervals.size(); i++) {
if(cur.end >= intervals[i].start)... 阅读全帖 |
|
w****g
发帖数: 3 | 22 我用的是先sort的解法。
http://www.yangsheep.net/wuyang/wordpress/?p=727
class Solution {
public:
struct mycmpclass {
bool operator() (Interval i,Interval j) { return (i.start < j.start); }
} mycmpobject;
vector merge(vector &intervals) {
vector ans;
if(intervals.empty()) return ans;
sort(intervals.begin(), intervals.end(), mycmpobject);
Interval cur=intervals[0];
for(int i = 1; i < intervals.size(); i++) {
if(cur.end >= intervals[i].start)... 阅读全帖 |
|
p*****2
发帖数: 21240 | 23 刚才又重写了一遍
class Solution1
{
TreeMap tm = new TreeMap();
void insert(Interval interval)
{
Integer prev = tm.floorKey(interval.start);
Integer next = tm.ceilingKey(interval.start);
if (prev != null && tm.get(prev) >= interval.start || next != null
&& interval.end >= next)
{
int start = -1;
if (prev != null && tm.get(prev) >= interval.start)
{
tm.put(pre... 阅读全帖 |
|
p*****2
发帖数: 21240 | 24 刚才又重写了一遍
class Solution1
{
TreeMap tm = new TreeMap();
void insert(Interval interval)
{
Integer prev = tm.floorKey(interval.start);
Integer next = tm.ceilingKey(interval.start);
if (prev != null && tm.get(prev) >= interval.start || next != null
&& interval.end >= next)
{
int start = -1;
if (prev != null && tm.get(prev) >= interval.start)
{
tm.put(pre... 阅读全帖 |
|
c*******u
发帖数: 47 | 25 求好心人帮我看看，想用in place, 就是过不了大的，折腾好久了，遇到这个的时候挂
了：
Last executed input
[[3,5],[12,15]], [6,6]
code:
class Solution {
public:
vector insert(vector &intervals, Interval newInterval) {
bool is_new_inserted = false;
for(vector::iterator it = intervals.begin(); it< intervals.end
(); it++){
if ((*it).end < newInterval.start){
continue;
}
if ((*it).start > newInterval.end){
if(!is_new_inserted){
intervals.insert(it, newInterval);
i... 阅读全帖 |
|
v*******n
发帖数: 41 | 26 public class Solution {
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList result = new ArrayList();
if(intervals.size() == 0){
result.add(newInterval);
return result;
}
for(Interval item:intervals){
if(item.end < newInterval.start){
result.add(item);
... 阅读全帖 |
|
g***j
发帖数: 1275 | 27 第一道，给定一堆的interval，起始点都是时间，精确到毫秒。然后再给一个interval
，判断这个这个新的interval，如果这个interval上存在某一点，同时和三个
interval相交，返回true， 否则返回false。
注意，是存在某单个点，同时和三个overlap，不是不同的点和三个overlap，也就是说
，如果它和三个inteval 有overlap，但是这三个interval没有overlap到同一点，也返
回false
比如，已有 [1,3),[2,6)，[4,7)，[2-5), 给定[1,7)，返回true, 给定[5,7)，返回
false
第二道，给定一堆的interval，起始点都是时间，再给定一个interval，返回所有的子
interval，跟给定的这一堆interval有两个以上的overlap
比如，已有 [1,3),[2,6)，[4,7)，给定[1,7)，返回[2,3)，[4,6)，给定[5,7)，返回[
5,6) |
|
d******0
发帖数: 22800 | 28 我刚跑了个类似的interval或者tempo或者LT我也不知道啥，反正是2迈快跑7分pace，1
迈jog10分pace，交叉着来。前头3。2迈warm up，后头3mile cool down。
发现一个问题，中间1迈jog更本心率恢复不到MAF的状态。每跑2迈快的时候，warm up
好心率是140，2迈里全是180上，1迈里最多恢复到160，上2迈快跑又是180。。。第3组
最后一迈有点累，感觉时间过得好慢啊。。。第三组开始的时候反倒很轻松。第2组2迈
快跑其实很舒服。不知道要做几组算合适，估计我撑一下，可以做个5组，但是第二天
肯定不能跑了。
Type Distance Split settings Duration Total Duration Pace
Avg HR Max HR Notes
1 Interval 3.2 mi 34:49.14 34:49.14 10:53 141 148
warm up
2 Interval 2.5 mi 17:33.... 阅读全帖 |
|
y******n
发帖数: 4527 | 29 今天早上跑了第二次interval，5*600m@5K pace.
第一次用305的interval option，却怎么也调不出pace。折腾了半天还是只有距离和休
息时间，不得已只好在起跑之后换到另外的模式来监控pace。哪位指点一下，305的
interval时怎么同时显示距离和pace？
跑的时候觉得非常不稳定，现在看看数据还好，只有第三个差的比较多，可能是结束前
听到警告的次数搞错了，提前减速了。
Interval 0.4 Mi 2:15.91 151 170
Interval 0.15 Mi 2:00 140 170
Interval 0.4 Mi 2:21.72 165 176
Interval 0.16 Mi 2:00 150 176
Interval 0.4 Mi 2:45.46 165 176
Interval 0.19 Mi |
|
z*********8
发帖数: 2070 | 30 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].
代码不好写啊， 谁给贴个？ |
|
z*********8
发帖数: 2070 | 31 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].
代码不好写啊， 谁给贴个？ |
|
r*********n
发帖数: 4553 | 32 O(logN) search implemented using STL set
void insert_interval(set>& intervals, const pair&
newint){
set last;
for(auto& r : intervals){
last.insert(r.second);
}
auto beg = last.lower_bound(newint.first);
auto end = intervals.lower_bound(make_pair(newint.second, 0));
if( (*end).first == newint.second ) ++end;
if( beg == end ){
intervals.insert(newint);
}else{
auto it = intervals.begin() + beg - last.begin();
... 阅读全帖 |
|
l*n
发帖数: 529 | 33 描述得看不懂啊。写了个感觉比较简明的，就是对所有不可再分的区间进行计数。
排序O(nlogn)+查找O(2*nlogn)+计数O(n*m)，其中m是平均区间分割数。
List mostOverlapped(Interval[] ints) {
Set set = new HashSet();
for (Interval itv : ints) {
set.add(itv.start);
set.add(itv.end);
}
// all candidate intervals;
List ends = new ArrayList(set);
Collections.sort(ends);
int max = 0;
// count overlapped times of each candidates
int[] counts = new int[ends.size()];
for (i... 阅读全帖 |
|
r*****y
发帖数: 199 | 34 small sample size的话，bootstrap interval， percentile interval， bootstrap
t interval， bias corrected interval， bias corrected and accelerated
interval都能用，而且没有固定哪一个最好。一般的study就用bootstrap interval或
者percentile interval就行了，bootstrap t和bootstrap的区别就相当于Ztest和
ttest的区别，bootstrap t你要double bootstrap来estimate你的Ztable。说的可能不
一定完全对，但上学期俺也就学了这点皮毛。 |
|
R*****t
发帖数: 2115 | 35 浏览跑版，阅读到由于天冷了，有些跑友将户外跑步转变用健身房的treadmill；也阅
读到因为其它原因，有些跑友购买了treadmill在家跑。这使我想起曾经阅读过的一篇
文章，现与朋友们分享（http://www.runnersworld.com/treadmills/inside-job）。
Inside Job
Survive winter treadmill running by doing interval, hill, and tempo workouts.
By Laurel Leicht (December 30, 2011； Runner's World)
When it comes to icy roads, even the toughest runners head for the 'mills.
But running inside doesn't have to compromise your workout—you can still
accomplish the purpose of your run with a few tweaks. First o... 阅读全帖 |
|
N******o
发帖数: 3053 | 36 看到版上一个个超人的速度，感悟到跑步还是要科学训练。读了很多帖子，发觉自己一
直都是Over training，几千Mile的Overtraining，好像身体已经无奈的接受了这个现
实。
我不喜欢跟计划，还是喜欢随心所欲的跑。于是最近每周加一次Interval和Tempo，还
是想根据心率来跑Interval和Tempo。我的MAF心率应该是140，但是一直都是>150心率
在跑，这个心率跑20mile也没有问题。最近增加Interval和Tempo跑。每周五次：一次
Interval，一次Tempo，三次随便跑。我估计我最大心率180.没有科学测量过，但是过
了175就要死要活的感觉，最大应该只能是180了吧。
Interval心率175：[email protected]
/* */[email protected]
/* */，跑6Mile
Tempo心率165：大概8.5MPH，跑8Mile
其他三次就是大概心率150，跑10mile。
这样的话是不是会有提高？不是很喜欢那个Tempo跑，是不是可以降低为150心率的
10mile跑？因为在Gym里面跑... 阅读全帖 |
|
f*********m
发帖数: 726 | 37 interval search算法在该书14.3节（第三版）。
对于下面的树([start，end](maximum end point value in the subtree of the node
))：
[16，21](30)
/ \
[8，9](23) [24，30](30)
/ \ / \
[5，8](8) [15，23](23) [17，19](19) [26，26](26)
若去搜索[22，25]的overlap interval,书上的算法只能找到左边的[15，23]，漏掉了
右边的[24，30]。
书上的算法只保证只找到一个。要找到所有的是不是需要同时搜索左右两个children？
这样复杂度会变成nlogn吧，不如直接做个线性search？
书上是用augmented tree来实现interval tree的，有没有其他形式的interval tree，
可以找到所有的... 阅读全帖 |
|
w****a
发帖数: 710 | 38 看来板上的mj，以及最近陆续拿到offer的朋友的mj。我发现interval在G家是热门题型。
我说几个印象深的，
1. merge intervals
2. insert interval
3. 一堆intervals查询某个点是否在interval里面。变体：给一堆pair（登录时间，退
出时间），给定某时间点求在线人数数量。
我感觉这些题既可以考基本的编程功底，也可以改编成online版本，这样也可以考察线
段树了。RMQ什么的都能上。确实是个好考点啊。 |
|
w****a
发帖数: 710 | 39 看来板上的mj，以及最近陆续拿到offer的朋友的mj。我发现interval在G家是热门题型。
我说几个印象深的，
1. merge intervals
2. insert interval
3. 一堆intervals查询某个点是否在interval里面。变体：给一堆pair（登录时间，退
出时间），给定某时间点求在线人数数量。
我感觉这些题既可以考基本的编程功底，也可以改编成online版本，这样也可以考察线
段树了。RMQ什么的都能上。确实是个好考点啊。 |
|
|
j*****n
发帖数: 1545 | 41 Interval tree 返回的是 所有 包括那个点的 interval.
我觉得挺有用的, 很多和 interval 有关的问题都能用到 interval tree. |
|
g*******s
发帖数: 2963 | 42 好像看到最近不少面经都出现了跟interval有关的。
到底什么情况下才需要当场先build一个interval tree然后再往下做？
我看了看leetcode上两道跟interval有关的（insert interval 和 merge interval）
都需要build整个tree么？ |
|
b*******e
发帖数: 123 | 43 所有端点排序，做一个counter,遇到开始端点+1,遇到结束端点-1。最大的counter对应
的端点们就是最多重复的区间。
O(nlog(n))
vector maxoverlap(vector inputs){
typedef pair ENDS;
// all end points sort.
vector preends;
for(const auto & x: inputs){
preends.push_back(make_pair(1,x.start));
preends.push_back(make_pair(-1,x.end));
}
sort(preends.begin(),preends.end(),[](ENDS a, ENDS b){
return a.second < b.second; });
//combine same end points.
vector ends;
int i = 0;
while... 阅读全帖 |
|
g***j
发帖数: 1275 | 44 在排序的时候，用到这个比较的function来排序这些intervals
sort(intervals.begin(), intervals.end(), isLess);
因为是按照x的坐标来比较的，为啥这里必须用 < 而不是<=，为啥用<= 就会错呢？
bool isLess(const Interval a, const Interval b) {
return a.start < b.start; // couldn't use <=
}
这是算法的问题，还是c++的问题？ |
|
i*********5
发帖数: 19210 | 45 给你推荐FIRST计划里的interval吧：
5. Put More Variety in Your Speedwork
Many runners do no speedwork at all. Those who do often fall into a rut,
running the same workout time after time. Pierce learned long ago that this
approach makes speedwork much harder than it should be. "I used to run the
same speed workout week after week," he recalls. "After a while, I would
start to dread that workout. Speedwork is much easier when you change it
around a lot." The FIRST runners do many different speed workouts at... 阅读全帖 |
|
m******a
发帖数: 77 | 46 大致作法应该是这样的
1. 你有一列数据点(y0, x0), 这里x应理解为N维矢量
你的模型是 y = f(x, c), c 是一列模型参数
在你建模型时, 你是要定出这一列参数 c, 同时你还应该得到对应的 Covariance
Matrix
通常的软件都提供这些信息
2. 有了Covariance Matrix后, 你可以生成很多列参数 c,
下面实际是作一些 Monte Carlo 模拟,
对应每一个数据点, 你都有很多 prediction - 因为每列c 给一个prediction
因此, 如果你有 D 个数据点的话,
你得到 D by D 的一个Covariance Matrix M -别和前面的Covariance Matrix混淆
3. 现在你可以算出来 Chi-Square
SUM( (y0 - y) M^-1 (y0 - y) )
同时, D 就是你的自由度数
有了这两个, 查表就知道你的 confidence level, 就是你的模型有多可靠
4. 关于你说的 confidence interval... 阅读全帖 |
|
s**x
发帖数: 7506 | 47 14.3-4
given an interval tree T and interval i, describe how all intervals in T
that overlap i can be listed in O(min(n, klogn)) time, where k is the number
of intervals in the output list. (optional: find a solution that does not
modify the tree)
14.3-7
VLSI databases commonly represent an intergrated circuit as a list of
rectangles, assume that each rectangle is rectilinearly oriented(side
parallel to the x- and y-axis), so that a representation of a rectangle
consists of its minimum and maxim... 阅读全帖 |
|
|
i**********e
发帖数: 1145 | 49 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
给个例子：
当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
很好的编程练习。 |
|
|
