logo
Redian新闻
>未名空间
>Money - 海外理财
>
chase万豪每年送的free night能给家人订吗？
avatar
chase万豪每年送的free night能给家人订吗？# Money - 海外理财
j*p
1 楼
给定一些不相交的区间和一个新的区间，要求合并起来
但问题是不让用新的vector/stack，也就是说要用constant additional space
请教大家
估计是挂了
avatar
k*0
2 楼
RT
可不可以加上additional guest的名字然后让他们去check in？ 多谢！
avatar
p*4
3 楼
merge interval?

【在 j*****p 的大作中提到】
: 给定一些不相交的区间和一个新的区间，要求合并起来
: 但问题是不让用新的vector/stack，也就是说要用constant additional space
: 请教大家
: 估计是挂了
avatar
i*i
4 楼
这个free night是不是只是category 1-4的？请问版上卖的category 1-5的是怎么来的
？
avatar
j*p
5 楼
对啊，这题不用新的vector或者是list怎么搞？

【在 p******4 的大作中提到】
: merge interval?
avatar
k*0
6 楼
1-4是开卡送的，1-5是每年交年费的时候送的吧？我问的是1-5的

【在 i***i 的大作中提到】
: 这个free night是不是只是category 1-4的？请问版上卖的category 1-5的是怎么来的
: ？
avatar
r*k
7 楼
老的排个序
新的挨个和老的比较
能merge就把老的删掉，更新新的interval
碰到不能merge，算法就可以结束

【在 j*****p 的大作中提到】
: 给定一些不相交的区间和一个新的区间，要求合并起来
: 但问题是不让用新的vector/stack，也就是说要用constant additional space
: 请教大家
: 估计是挂了
avatar
M*a
8 楼
不用排序应该就可以，一个个和老的比。如果有哪个老的完全包含新的就结束，如果新
的完全包含老的老的删除，剩下的情况就是最多有两个老的分别和新的的上下边界相交
排序还要nlogn呢

【在 r*******k 的大作中提到】
: 老的排个序
: 新的挨个和老的比较
: 能merge就把老的删掉，更新新的interval
: 碰到不能merge，算法就可以结束
avatar
r*k
9 楼
我觉得根本不用考虑那么多
就遍历一下，能合并就删老的
一遍就行了
因为老的彼此都是不想交的

【在 M*******a 的大作中提到】
: 不用排序应该就可以，一个个和老的比。如果有哪个老的完全包含新的就结束，如果新
: 的完全包含老的老的删除，剩下的情况就是最多有两个老的分别和新的的上下边界相交
: 排序还要nlogn呢
avatar
M*a
10 楼
我就这个意思

【在 r*******k 的大作中提到】
: 我觉得根本不用考虑那么多
: 就遍历一下，能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的
avatar
t*e
11 楼
应该还有其他可能吧，比如新的区间落在两个老区间中间呢？还是说题目要求合并，所
以必然会有相交，而不用考虑这种情况

【在 M*******a 的大作中提到】
: 不用排序应该就可以，一个个和老的比。如果有哪个老的完全包含新的就结束，如果新
: 的完全包含老的老的删除，剩下的情况就是最多有两个老的分别和新的的上下边界相交
: 排序还要nlogn呢
avatar
M*a
12 楼
那就什么都不用干啊，下一个阿

【在 t*******e 的大作中提到】
: 应该还有其他可能吧，比如新的区间落在两个老区间中间呢？还是说题目要求合并，所
: 以必然会有相交，而不用考虑这种情况
avatar
t*e
13 楼
重新想了一下，这和leetcode上的insert intervals 做法应该一样吧，虽然那个原始
区间都排过序了
avatar
j*p
14 楼
可是在c++中的vector或者是java中的List的iterator的时候，怎样能够删除又不引起
invalid iterator或者是concurrent modification exception呢？
能给个程序吗？我看到的解答都是创建新的vector或者是List

【在 r*******k 的大作中提到】
: 老的排个序
: 新的挨个和老的比较
: 能merge就把老的删掉，更新新的interval
: 碰到不能merge，算法就可以结束
avatar
U*A
15 楼
这个怎么样？
/*
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
avatar
l*a
16 楼
你可以连续调用
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
avatar
j*3
17 楼
排序然后binary search
avatar
l*a
18 楼
结果不需要顺序的话
你为什么要排序

【在 j**********3 的大作中提到】
: 排序然后binary search
avatar
j*p
19 楼
这里的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;
: }
avatar
U*A
20 楼
为什么耗时？
你怎么该的？

【在 j*****p 的大作中提到】
: 这里的vector.erase非常耗时吧?
: 我改了之后没有能够在leetcode上通过测试
avatar
j*p
21 楼
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 的大作中提到】
: 为什么耗时？
: 你怎么该的？
avatar
j*p
22 楼
能否给个代码？我还自认为比较熟java，但发现硬是没有搞出来

【在 l*****a 的大作中提到】
: 你可以连续调用
: list.remove(cur)
: 相当于把list中cur,cur+1,cur+2..删除
: 然后list.insert(cur,**)
: 就是插在当前位置
avatar
r*k
23 楼
不能先记下index，然后最后统一删除么？
啊，晕，这就相当于新建了List……
那从List的后面向前用index扫描呢？
碰到合并的就删除，这个没问题吧？

【在 j*****p 的大作中提到】
: 可是在c++中的vector或者是java中的List的iterator的时候，怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢？
: 能给个程序吗？我看到的解答都是创建新的vector或者是List
avatar
U*A
24 楼
那是因为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; iif(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++;
avatar
j*p
25 楼
怪了，之前我的提交说是用时太长了

【在 U***A 的大作中提到】
: 那是因为lc是排序的。所有最后应该找合适的位置插入newInterval.
: 这个可以
: vector insert(vector &intervals, Interval
: newInterval) {
: int size = (int) intervals.size();
: if (size == 0) {
: intervals.push_back(newInterval);
: return intervals;
: }
:
avatar
j*p
26 楼
您要不写个例程给示范下？

【在 r*******k 的大作中提到】
: 不能先记下index，然后最后统一删除么？
: 啊，晕，这就相当于新建了List……
: 那从List的后面向前用index扫描呢？
: 碰到合并的就删除，这个没问题吧？
avatar
j*3
27 楼
不排序咋binary search？
不用额外空间的话，就需要多次iteration？这样time complexity就增加了。。。

【在 l*****a 的大作中提到】
: 结果不需要顺序的话
: 你为什么要排序
avatar
l*7
28 楼
vector 的 erase()复杂度是O(n)啊，岂不费时？最坏就O(n^2)了。设想新的区间包含
所有已知区间。
在erase那里可以考虑把最后一个区间swap过来；或者在线partition，最后删除重合的
区间就行了。

【在 U***A 的大作中提到】
: 为什么耗时？
: 你怎么该的？
avatar
j*p
29 楼
对，之前我就是因为这个而超时了

【在 l*****7 的大作中提到】
: vector 的 erase()复杂度是O(n)啊，岂不费时？最坏就O(n^2)了。设想新的区间包含
: 所有已知区间。
: 在erase那里可以考虑把最后一个区间swap过来；或者在线partition，最后删除重合的
: 区间就行了。
avatar
t*e
30 楼
上面用iterator的方法是不错，不过这还算是O(1) space么
avatar
s*n
31 楼
一遍肯定不行啊

【在 r*******k 的大作中提到】
: 我觉得根本不用考虑那么多
: 就遍历一下，能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的
avatar
l*1
32 楼
还是要排序吧，因为老的和新的合并后的新区间可能和其它老区间重合。除非题目没要
求合并所有重合区间。
avatar
x*9
34 楼
+1

【在 t*******e 的大作中提到】
: 重新想了一下，这和leetcode上的insert intervals 做法应该一样吧，虽然那个原始
: 区间都排过序了
avatar
a*y
35 楼
看了大家的回复，得到启发，思路如下：
遍历两遍：第一遍确定如下情况：
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);
}
avatar
M*M
36 楼
同意!
如果像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 的大作中提到】
: 我觉得根本不用考虑那么多
: 就遍历一下，能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的
avatar
g*y
37 楼
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;
}
相关阅读
ink bold 和 ink plusAmex Blue Preferred 能转成Amex Blue cash everyday吗？最近有哪些卡bonus不错啊？SW兑换短途里程票的优势AMEX BCP的rewards dollar怎么用这笔钱我该不该付？求推荐一张hotel卡citi ThankYou帐户也被锁从国内汇美金过来，开gift letter，必须是直系亲属吗？怎么理解discover 6月份的cashback？ 最多消费500 还是最多cashback=500？理性决策的故事最近有人关SPG收到rention offer的么？求助！！credit report里显示SSN有问题在加油站买油卡算加油站的消费吗？Discover：Get rewarded with 2% 是5%+2%吗居然在united的account里刷出了50k+5k的offer美国鹰洋银币送包子，求Chase checking coupon (No DD)怎么实现用信用卡付房贷2包子求GW $0.01
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。