Shipping update for N4 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

Shipping update for N4

Shipping update for N4# PDA - 掌中宝

s*e2012-11-15 08:11

1 楼

Given 2 range array, output the intersection array.
a: [1,5], [8,15], [30,90]
b: [2,7],[12,18],[80,100]
output:
[2,5],[12,15],[80,90]

m*g2012-11-15 08:11

2 楼

没有delivery estimate

b*c2012-11-15 08:11

3 楼

赞，sort+merge

c*c2012-11-15 08:11

4 楼

中国移动？

f*t2012-11-15 08:11

5 楼

interval tree?

m*g2012-11-15 08:11

6 楼

哦，我也可以改成中国联通，呵呵。

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

: 中国移动？

B*12012-11-15 08:11

7 楼

isn't it
output:
[2,5],[12,15],[80,90]

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

: Given 2 range array, output the intersection array.
: a: [1,5], [8,15], [30,90]
: b: [2,7],[12,18],[80,100]
: output:
: [2,5],[12,15],[80,90]

g*i2012-11-15 08:11

8 楼

不用interval tree, linear扫一遍就可以了.楼主给的output确实错了,呵呵.
话说palantir待遇如何有人知道吗?

k*n2012-11-15 08:11

9 楼

are they sorted?

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

: Given 2 range array, output the intersection array.
: a: [1,5], [8,15], [30,90]
: b: [2,7],[12,18],[80,100]
: output:
: [2,5],[12,15],[80,90]

l*y2012-11-15 08:11

10 楼

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Segment {
int from, to;
};
struct cmp {
bool operator() (const Segment& s1, const Segment& s2) {
return s1.from < s2.from;
}
};
bool GetOverlap(Segment& s1, Segment& s2, Segment& inter)
{
bool result = false;
if (s1.to > s2.from && s2.to > s1.from) {
result = true;
inter.from = max(s1.from, s2.from);
inter.to = min(s1.to, s2.to);
}
return result;
}
int main() {
freopen("input","r",stdin);
int numofcase;
cin >> numofcase;
for (int cc = 1; cc <= numofcase; cc++) {
vector v1;
vector v2;
Segment segment;
int index, num;
cin >> index;
for (int i = 0; i < index; i++) {
cin >> segment.from >> segment.to;
v1.push_back(segment);
}
cin >> index;
for (int i = 0; i < index; i++) {
cin >> segment.from >> segment.to;
v2.push_back(segment);
}
sort(v1.begin(), v1.end(), cmp());
sort(v2.begin(), v2.end(), cmp());
int i1 = 0;
int i2 = 0;
vector result;
while (i1 < v1.size() && i2 < v2.size()) {
Segment inter;
if (GetOverlap(v1[i1], v2[i2], inter)) {
result.push_back(inter);
}
if (v1[i1].to <= v2[i2].to) {
i1++;
} else {
i2++;
}
}
for (int i = 0; i < result.size(); i++) {
cout << result[i].from << " " << result[i].to << endl;
}
}
return 0;
}
Input:
1
3 1 5 8 15 30 90
3 2 7 12 18 80 100
Output:
2 5
12 15
80 90