[求购]amazon 20%off diapers coupon W开头 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

[求购]amazon 20%off diapers coupon W开头

[求购]amazon 20%off diapers coupon W开头# PennySaver - 省钱一族

c*g2010-08-12 07:08

1 楼

有n个interval，like this [1,7) [2,4) [5,8) [4,5) [3,6) 找出与这些interval相
交的最多次数的点的集合。
应该返回， [3,4), [4,5), [5,6) 这三个集合分别重叠了三次，是最多的，没有重叠
四次的区间。
我想到的办法是，不断的求两两的overlap，直到没有了为止，但是这样时间复杂度很
高，另外，我还不知道对不对，还存在去重复的情况，比如给定 [1, 5), [1,5), [1,
5), 两两求overlap，始终都是这个。

l*r2010-08-12 07:08

2 楼

不建议交易打印胖子；胖子是免费的，收费的是服务:
求一张amazon 20% off diapers coupon W打头
所求物品名称:
amazon 20%off diapers coupon W打头
物品类别（coupon: mfc 等；血糖仪等）:
求一张amazon 20% off diapers coupon，要求是W打头的
物品来源（报纸夹页，厂家邮寄等）:
parents杂志里面的
可接受的价格（必须明码标价，必填）:
$2.00+5个包子，不需要邮寄，把coupon code发我就成
邮寄损失方式哪方承担（若需邮寄，必填）:
N/A
付款方式说明:
non-cc paypal
本贴有效期（必填）:
till got
联系方式（例：站内）:
站内PM

c*g2010-08-12 07:08

3 楼

有人谈谈这个么？

1,

【在 c***g 的大作中提到】

: 有n个interval，like this [1,7) [2,4) [5,8) [4,5) [3,6) 找出与这些interval相
: 交的最多次数的点的集合。
: 应该返回， [3,4), [4,5), [5,6) 这三个集合分别重叠了三次，是最多的，没有重叠
: 四次的区间。
: 我想到的办法是，不断的求两两的overlap，直到没有了为止，但是这样时间复杂度很
: 高，另外，我还不知道对不对，还存在去重复的情况，比如给定 [1, 5), [1,5), [1,
: 5), 两两求overlap，始终都是这个。

m*p2010-08-12 07:08

4 楼

不会啊。

s*r2010-08-12 07:08

5 楼

完全不一样的问题同学

s*r2010-08-12 07:08

6 楼

区间们一般喜欢被排序处理
然后第一步扫描可以先确定最多的重叠次数
看到开始 +1，结束 -1，这样统计出最大的
第二遍这样做的时候总是记住最后的开始点而且根据和第一遍一样的统
计可以知道什么时候的结束点对应一个解了

b*e2010-08-12 07:08

7 楼

所有端点排序，做一个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(i < preends.size()){
if(ends.empty() || preends[i].second != ends.back().second)
ends.push_back(preends[i]);
else
ends.back().first += preends[i].first;
++i;
}
//count to find the maxmum interval
vector > marks;
int sum = 0;
for(int i = 0 ; i < ends.size(); ++i){
if(ends[i].first==0) continue;
sum += ends[i].first;
if(ends[i].first>0){
while(marks.size() < sum)
marks.push_back(vector());
marks[sum-1].push_back(ends[i]);
}
else
marks[sum-ends[i].first-1].push_back(ends[i]);
}
// output.
vector res;
for(int i = 0 ; i < marks.back().size()/2; ++i){
res.push_back(Interval(marks.back()[2*i].second,marks.back()[2*i+1].
second));
}
return res;
}

l*n2010-08-12 07:08

8 楼

描述得看不懂啊。写了个感觉比较简明的，就是对所有不可再分的区间进行计数。
排序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 (int i = 0; i < ints.length; i++) {
int si = bsearch(ints[i].start, ends, 0, ends.size());
int ei = bsearch(ints[i].end, ends, 0, ends.size());
for (int j = si; j < ei; j++) {
counts[j]++;
if (counts[j] > max)
max = counts[j];
}
}
List al = new ArrayList();
for (int i = 0; i < ends.size() - 1; i++) {
if (counts[i] == max)
al.add(new Interval(ends.get(i), ends.get(i + 1)));
}
return al;
}
int bsearch(int x, List ends, int i, int j) {
if (i == j)
return -1;
int m = (i + j) / 2;
int y = ends.get(m);
if (y == x) {
return m;
} else {
if (y < x) {
return bsearch(x, ends, m + 1, j);
} else {
return bsearch(x, ends, i, m);
}
}
}

【在 s*****r 的大作中提到】

: 区间们一般喜欢被排序处理
: 然后第一步扫描可以先确定最多的重叠次数
: 看到开始 +1，结束 -1，这样统计出最大的
: 第二遍这样做的时候总是记住最后的开始点而且根据和第一遍一样的统
: 计可以知道什么时候的结束点对应一个解了

s*r2010-08-12 07:08

9 楼

写麻烦了，只要扫两遍就好，O(n log n) + O(n) + O(n)
空间上也只需要一个输出数组 O(n)
不过没有仔细想是否正确
sort(points, cmp)
maxn, count = 0, 0
for p in points
(p.start?) ? (++count) : (--count)
maxn = max(maxn, count)
ret = []
count = 0
last_start = nil
for p in points
if p.start?
++count
last_start = p
else
if count == maxn
ret << [last_start.val, p.val]
--count
ret

【在 l*n 的大作中提到】

: 描述得看不懂啊。写了个感觉比较简明的，就是对所有不可再分的区间进行计数。
: 排序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);

l*n2010-08-12 07:08

10 楼

嗯，你这个应该是对的。只是这个count++/--一开始会感觉比较tricky，不容易适应。

【在 s*****r 的大作中提到】

: 写麻烦了，只要扫两遍就好，O(n log n) + O(n) + O(n)
: 空间上也只需要一个输出数组 O(n)
: 不过没有仔细想是否正确
: sort(points, cmp)
: maxn, count = 0, 0
: for p in points
: (p.start?) ? (++count) : (--count)
: maxn = max(maxn, count)
: ret = []
: count = 0

m*k2010-08-12 07:08

11 楼

排序后，一次扫描就够了吧，
overlapMost = [0, 0, 0],
lastStart = 0
for p in sortedPoints
if (p.start?) {
lastStart = p,
counter＋＋ ,
}
else{
if(counter >overlapMost[2] ){
overlapMost = [lastStart, p, counter]
}
counter--
}
return overlapMost.
所有的段都是 [) ， it makes life easier.

s*r2010-08-12 07:08

12 楼

楼主样例输出所有解
一次扫是可以只是如果发现给好的解要重新更新 ret 数组
如果不想 ret.clear 之后再添加的话
要用一个计数记录当前解的个数，如果被更新了计数要清零

【在 m*****k 的大作中提到】

: 排序后，一次扫描就够了吧，
: overlapMost = [0, 0, 0],
: lastStart = 0
: for p in sortedPoints
: if (p.start?) {
: lastStart = p,
: counter＋＋ ,
: }
: else{
: if(counter >overlapMost[2] ){

m*k2010-08-12 07:08

13 楼

要输出所有解啊, 大意了。
那就改一小下：
overlapMost = {[0, 0, 0]}
lastStart = 0
for p in sortedPoints
if (p.start?) {
lastStart = p,
counter＋＋ ,
}
else{
if(counter >overlapMost.get(0)[2] ){
overlapMost = {[lastStart, p, counter]}
}
else if(counter == overlapMost.get(0)[2] ){
overlapMost .add ([lastStart, p, counter])
}
counter--
}
return overlapMost.

d*u2010-08-12 07:08

14 楼

不用扫两边吧第一遍的时候用个set存着最大重叠的数一边更新

【在 s*****r 的大作中提到】

s*r2010-08-12 07:08

15 楼

overlapMost = {[lastStart, p, counter]}
这一步可能隐含着大量垃圾回收和创建新数组不是最优的做法不过是挺好的描述

【在 m*****k 的大作中提到】

: 要输出所有解啊, 大意了。
: 那就改一小下：
: overlapMost = {[0, 0, 0]}
: lastStart = 0
: for p in sortedPoints
: if (p.start?) {
: lastStart = p,
: counter＋＋ ,
: }
: else{

s*r2010-08-12 07:08

16 楼

之前已经说了可以只一遍也分析了一遍的时候要注意的问题
像你这样做和 madmonk 的解法是一样的重新更新 set 看似是一个 O(1) 的赋值
其实隐含着销毁和创建数组虽然均摊并没有增加算法复杂度但并不是最快的做法
扫两遍易于描述也可以给 ret 预留足够空间直接不用动态增长
你看不到的操作可能远多于之前的一遍扫

【在 d**********u 的大作中提到】

: 不用扫两边吧第一遍的时候用个set存着最大重叠的数一边更新

s*t2010-08-12 07:08

17 楼

干嘛要排序啊，直接扫描一遍，用数组记录最大（and跟最大一样的不就完了），On

s*t2010-08-12 07:08

18 楼

就一个数组，也不用什么回收啊

s*r2010-08-12 07:08

19 楼

排序是必须的不解释只是如果区间范围小可以统计而已空间换时间
回收的是次优解数组里的所有区间当然这个最坏才总共n-2个外加ret动态增长的消耗
均摊还是 O(1)
只是讨论下细节当然一遍写起来漂亮但实际工作量未必少如果明白就没必要纠结是
一遍还是两遍

【在 s******t 的大作中提到】

: 干嘛要排序啊，直接扫描一遍，用数组记录最大（and跟最大一样的不就完了），On