j*****p
发帖数: 41 | 1 给定一些不相交的区间和一个新的区间，要求合并起来
但问题是不让用新的vector/stack，也就是说要用constant additional space
请教大家
估计是挂了 |
p******4
发帖数: 31 | 2 merge interval?
【在 j*****p 的大作中提到】
: 给定一些不相交的区间和一个新的区间，要求合并起来
: 但问题是不让用新的vector/stack，也就是说要用constant additional space
: 请教大家
: 估计是挂了
|
j*****p
发帖数: 41 | 3 对啊，这题不用新的vector或者是list怎么搞？
【在 p******4 的大作中提到】
: merge interval?
|
r*******k
发帖数: 1423 | 4 老的排个序
新的挨个和老的比较
能merge就把老的删掉，更新新的interval
碰到不能merge，算法就可以结束
【在 j*****p 的大作中提到】
: 给定一些不相交的区间和一个新的区间，要求合并起来
: 但问题是不让用新的vector/stack，也就是说要用constant additional space
: 请教大家
: 估计是挂了
|
M*******a
发帖数: 1633 | 5 不用排序应该就可以，一个个和老的比。如果有哪个老的完全包含新的就结束，如果新
的完全包含老的老的删除，剩下的情况就是最多有两个老的分别和新的的上下边界相交
排序还要nlogn呢
【在 r*******k 的大作中提到】
: 老的排个序
: 新的挨个和老的比较
: 能merge就把老的删掉，更新新的interval
: 碰到不能merge，算法就可以结束
|
r*******k
发帖数: 1423 | 6 我觉得根本不用考虑那么多
就遍历一下，能合并就删老的
一遍就行了
因为老的彼此都是不想交的
【在 M*******a 的大作中提到】
: 不用排序应该就可以，一个个和老的比。如果有哪个老的完全包含新的就结束，如果新
: 的完全包含老的老的删除，剩下的情况就是最多有两个老的分别和新的的上下边界相交
: 排序还要nlogn呢
|
M*******a
发帖数: 1633 | 7 我就这个意思
【在 r*******k 的大作中提到】
: 我觉得根本不用考虑那么多
: 就遍历一下，能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的
|
t*******e
发帖数: 274 | 8 应该还有其他可能吧，比如新的区间落在两个老区间中间呢？还是说题目要求合并，所
以必然会有相交，而不用考虑这种情况
【在 M*******a 的大作中提到】
: 不用排序应该就可以，一个个和老的比。如果有哪个老的完全包含新的就结束，如果新
: 的完全包含老的老的删除，剩下的情况就是最多有两个老的分别和新的的上下边界相交
: 排序还要nlogn呢
|
M*******a
发帖数: 1633 | 9 那就什么都不用干啊，下一个阿
【在 t*******e 的大作中提到】
: 应该还有其他可能吧，比如新的区间落在两个老区间中间呢？还是说题目要求合并，所
: 以必然会有相交，而不用考虑这种情况
|
t*******e
发帖数: 274 | 10 重新想了一下，这和leetcode上的insert intervals 做法应该一样吧，虽然那个原始
区间都排过序了 |
|
|
j*****p
发帖数: 41 | 11 可是在c++中的vector或者是java中的List的iterator的时候，怎样能够删除又不引起
invalid iterator或者是concurrent modification exception呢？
能给个程序吗？我看到的解答都是创建新的vector或者是List
【在 r*******k 的大作中提到】
: 老的排个序
: 新的挨个和老的比较
: 能merge就把老的删掉，更新新的interval
: 碰到不能merge，算法就可以结束
|
U***A
发帖数: 849 | 12 这个怎么样？
/*
merege interals
*/
void mergeIntervals(vector &vp, Pair np){
int size = (int)vp.size();
if(size == 0) {
vp.push_back(np);
return;
}
for(vector::iterator it = vp.begin(); it != vp.end();){
if(np.first > it->second || np.second < it->first){
it++;
}
else if(np.first > it->first && np.second < it->second){
return;
}
else if(np.first <= it->first && np.second >= it->second){
vp.erase(it);
}
else{
np.first = np.first < it->first ? np.first : it->first;
np.second = np.second > it->second? np.second : it->second;
vp.erase(it);
}
}
vp.push_back(np);
}
【在 j*****p 的大作中提到】
: 可是在c++中的vector或者是java中的List的iterator的时候，怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢？
: 能给个程序吗？我看到的解答都是创建新的vector或者是List
|
l*****a
发帖数: 14598 | 13 你可以连续调用
list.remove(cur)
相当于把list中cur,cur+1,cur+2..删除
然后list.insert(cur,**)
就是插在当前位置
【在 j*****p 的大作中提到】
: 可是在c++中的vector或者是java中的List的iterator的时候，怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢？
: 能给个程序吗？我看到的解答都是创建新的vector或者是List
|
j**********3
发帖数: 3211 | |
l*****a
发帖数: 14598 | 15 结果不需要顺序的话
你为什么要排序
【在 j**********3 的大作中提到】
: 排序然后binary search
|
j*****p
发帖数: 41 | 16 这里的vector.erase非常耗时吧?
我改了之后没有能够在leetcode上通过测试
【在 U***A 的大作中提到】
: 这个怎么样？
: /*
: merege interals
: */
: void mergeIntervals(vector &vp, Pair np){
: int size = (int)vp.size();
: if(size == 0) {
: vp.push_back(np);
: return;
: }
|
U***A
发帖数: 849 | 17 为什么耗时？
你怎么该的？
【在 j*****p 的大作中提到】
: 这里的vector.erase非常耗时吧?
: 我改了之后没有能够在leetcode上通过测试
|
j*****p
发帖数: 41 | 18 vector insert(vector &intervals, Interval newInterval) {
int size = (int) intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
for (vector::iterator it = intervals.begin(); it != intervals.
end();) {
if (newInterval.start > it->end || newInterval.end < it->start) {
it++;
} else if (newInterval.start > it->start && newInterval.end < it->
end) {
return intervals;
} else if (newInterval.start <= it->start && newInterval.end >= it->
end) {
it = intervals.erase(it);
} else {
newInterval.start = newInterval.start < it->start ? newInterval.
start : it->start;
newInterval.end = newInterval.end > it->end ? newInterval.end :
it->end;
it = intervals.erase(it);
}
}
intervals.push_back(newInterval);
return intervals;
}
【在 U***A 的大作中提到】
: 为什么耗时？
: 你怎么该的？
|
j*****p
发帖数: 41 | 19 能否给个代码？我还自认为比较熟java，但发现硬是没有搞出来
【在 l*****a 的大作中提到】
: 你可以连续调用
: list.remove(cur)
: 相当于把list中cur,cur+1,cur+2..删除
: 然后list.insert(cur,**)
: 就是插在当前位置
|
r*******k
发帖数: 1423 | 20 不能先记下index，然后最后统一删除么？
啊，晕，这就相当于新建了List……
那从List的后面向前用index扫描呢？
碰到合并的就删除，这个没问题吧？
【在 j*****p 的大作中提到】
: 可是在c++中的vector或者是java中的List的iterator的时候，怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢？
: 能给个程序吗？我看到的解答都是创建新的vector或者是List
|
|
|
U***A
发帖数: 849 | 21 那是因为lc是排序的。所有最后应该找合适的位置插入newInterval.
这个可以
vector insert(vector &intervals, Interval
newInterval) {
int size = (int) intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
for (vector::iterator it = intervals.begin(); it != intervals.
end();) {
if (newInterval.start > it->end || newInterval.end < it->start) {
it++;
} else if (newInterval.start > it->start && newInterval.end < it->
end) {
return intervals;
} else if (newInterval.start <= it->start && newInterval.end >= it->
end) {
it = intervals.erase(it);
} else {
newInterval.start = newInterval.start < it->start ? newInterval.
start : it->start;
newInterval.end = newInterval.end > it->end ? newInterval.end :
it->end;
it = intervals.erase(it);
}
}
for(int i=0; i
if(newInterval.end < intervals[i].start){
intervals.insert(intervals.begin()+i, newInterval);
return intervals;
}
}
intervals.push_back(newInterval);
return intervals;
}
{
intervals.
【在 j*****p 的大作中提到】
: vector insert(vector &intervals, Interval newInterval) {
: int size = (int) intervals.size();
: if (size == 0) {
: intervals.push_back(newInterval);
: return intervals;
: }
: for (vector::iterator it = intervals.begin(); it != intervals.
: end();) {
: if (newInterval.start > it->end || newInterval.end < it->start) {
: it++;
|
j*****p
发帖数: 41 | 22 怪了，之前我的提交说是用时太长了
【在 U***A 的大作中提到】
: 那是因为lc是排序的。所有最后应该找合适的位置插入newInterval.
: 这个可以
: vector insert(vector &intervals, Interval
: newInterval) {
: int size = (int) intervals.size();
: if (size == 0) {
: intervals.push_back(newInterval);
: return intervals;
: }
:
|
j*****p
发帖数: 41 | 23 您要不写个例程给示范下？
【在 r*******k 的大作中提到】
: 不能先记下index，然后最后统一删除么？
: 啊，晕，这就相当于新建了List……
: 那从List的后面向前用index扫描呢？
: 碰到合并的就删除，这个没问题吧？
|
j**********3
发帖数: 3211 | 24 不排序咋binary search？
不用额外空间的话，就需要多次iteration？这样time complexity就增加了。。。
【在 l*****a 的大作中提到】
: 结果不需要顺序的话
: 你为什么要排序
|
l*****7
发帖数: 55 | 25 vector 的 erase()复杂度是O(n)啊，岂不费时？最坏就O(n^2)了。设想新的区间包含
所有已知区间。
在erase那里可以考虑把最后一个区间swap过来；或者在线partition，最后删除重合的
区间就行了。
【在 U***A 的大作中提到】
: 为什么耗时？
: 你怎么该的？
|
j*****p
发帖数: 41 | 26 对，之前我就是因为这个而超时了
【在 l*****7 的大作中提到】
: vector 的 erase()复杂度是O(n)啊，岂不费时？最坏就O(n^2)了。设想新的区间包含
: 所有已知区间。
: 在erase那里可以考虑把最后一个区间swap过来；或者在线partition，最后删除重合的
: 区间就行了。
|
t*******e
发帖数: 274 | 27 上面用iterator的方法是不错，不过这还算是O(1) space么 |
s*****n
发帖数: 350 | 28 一遍肯定不行啊
【在 r*******k 的大作中提到】
: 我觉得根本不用考虑那么多
: 就遍历一下，能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的
|
l**********1
发帖数: 415 | 29 还是要排序吧，因为老的和新的合并后的新区间可能和其它老区间重合。除非题目没要
求合并所有重合区间。 |
r*******e
发帖数: 971 | |
|
|
x******9
发帖数: 473 | 31 +1
【在 t*******e 的大作中提到】
: 重新想了一下，这和leetcode上的insert intervals 做法应该一样吧，虽然那个原始
: 区间都排过序了
|
a*****y
发帖数: 22 | 32 看了大家的回复，得到启发，思路如下：
遍历两遍：第一遍确定如下情况：
1， 新区间可以被原有的某个区间包含，直接返回
2， 新区间与原有的区间都不相交，push_back，返回
3， 相交，又分为两种情况：（1）新区间完全覆盖原有某区间，将改区间置为无效（
opening > close） （2）部分相交：更新新区间的头或尾，将原有的那个区间置为无效
第二遍遍历，删掉标记为无效的区间
总时间复杂度为O（n）
struct Interval {
int opening;
int close;
};
void MergeInterval(std::vector& org, Interval new_interval) {
int n = org.size();
if (n == 0) {
return;
}
bool is_intersected = false;
for (int i = 0; i < n; ++i) {
if (org[i].opening <= new_interval.opening) {
if (org[i].close >= new_interval.close) {
return;
} else if (org[i].close < new_interval.opening) {
continue;
}
is_intersected = true;
new_interval.opening = org[i].opening;
org[i].close = org[i].opening - 1;
} else {
if (new_interval.close < org[i].opening) {
continue;
} else if (new_interval.close < org[i].close) {
new_interval.close = org[i].close;
}
is_intersected = true;
org[i].close = org[i].opening - 1;
}
}
org.push_back(new_interval);
if (!is_intersected) {
return;
}
int deleted_num = 0;
for (int i = 0; i + deleted_num < n; ) {
if (org[i + deleted_num].opening > org[i + deleted_num].close) {
++deleted_num;
continue;
}
if (deleted_num > 0) {
org[i].opening = org[i + deleted_num].opening;
org[i].close = org[i + deleted_num].close;
}
++i;
}
org.resize(n - deleted_num);
} |
M*****M
发帖数: 20 | 33 同意!
如果像leetcode insert interval里区间vector已经排序，不用创建新vector， 只需
一步erase 和 insert， O(n)
vector insert(vector &intervals, Interval
newInterval) {
auto start = intervals.begin();
auto it= start;
for(; it !=intervals.end(); ++it) {
if(newInterval.endstart) {
//insert newinterval here
//before insertion, erase prev intervals which are already
merged to newinterval
it = intervals.erase(start, it);
intervals.insert(it, newInterval);
return intervals;
} else if (newInterval.start>it->end){
//newinterval has bigger start
start++;
} else {
//cur interval and newinterval have overlap
newInterval.start = min(it->start, newInterval.start);
newInterval.end = max(it->end, newInterval.end);
}
}
if(start!=it) {
//this is the case that newinterval includes all intervals
it = intervals.erase(start, it);
}
intervals.insert(it, newInterval);
return intervals;
}
如果区间vector没排序，就一个一个删
vector insert(vector &intervals, Interval
newInterval) {
auto it= intervals.begin();
for(; it !=intervals.end(); ) {
if(newInterval.endstart||newInterval.start>it->end) {
it++;
} else {
//cur interval and newinterval have overlap
newInterval.start = min(it->start, newInterval.start);
newInterval.end = max(it->end, newInterval.end);
it = intervals.erase(it);
}
}
intervals.insert(it, newInterval);
return intervals;
}
【在 r*******k 的大作中提到】
: 我觉得根本不用考虑那么多
: 就遍历一下，能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的
|
g*****y
发帖数: 94 | 34 Java 版的in-place，只能说实现起来太恶心啦。
public List insert(List intervals, Interval newInterval)
{
if (intervals == null) {
return intervals;
} else if (intervals.size() == 0) {
intervals.add(newInterval);
return intervals;
}
int size = intervals.size();
int left = findLastLess(intervals, newInterval);
int right = findFirstLarger(intervals, newInterval);
if (left < 0 || newInterval.start > intervals.get(left).end) {
++left;
}
if (right >= size || newInterval.end < intervals.get(right).start) {
--right;
}
for (int i = left; i <= right; ++i) {
newInterval.start = Math.min(newInterval.start, intervals.get(
left).start);
newInterval.end = Math.max(newInterval.end, intervals.get(left).
end);
intervals.remove(left);
}
intervals.add(left, newInterval);
return intervals;
}
private static int findLastLess(List intervals,
Interval newInterval) {
int low = 0, high = intervals.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (newInterval.start < intervals.get(mid).start) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return high;
}
private static int findFirstLarger(List intervals,
Interval newInterval) {
int low = 0, high = intervals.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (newInterval.end <= intervals.get(mid).end) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
} |
