http://www.itint5.com/oj/#14
要记录原来的索引，所以用了额外的空间，新生成一个结构。如果要省空间，可以用指针来排序，最后拿指针减去索引0的位置就是index，见：http://www.itint5.com/discuss/172/%E4%B8%BA%E5%95%A5%E6%88%91%E8%BF%99%E9%A2%98%E5%9C%A8%E5%A4%A7%E6%95%B0%E6%8D%AE%E6%97%B6%E4%BC%9Asegmentation-fault
这里没有用指针，也有很多错误，足可见面试时不要自取其辱，寻找合理的方法即可。
一要注意，sort和comp函数，因为是高级的，所以返回bool，并且参数是const引用。二要注意，排完序后，并不是前一个和后一个比较就行了，要记录之前的end最大的那个。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
struct
IntervalPair {
int
start;
int
end;
int
idx;
};bool
comp(const
IntervalPair &pa, const
IntervalPair &pb) {
if
(pa.start != pb.start) {
return
pa.start < pb.start;
} else
{
return
pb.end < pb.end;
}
}void
intersected(vector<Interval> &intervals, vector<bool> &isIntersected) {
int
size = intervals.size();
if
(size <= 1) return;
vector<IntervalPair> vec(size);
for
(int
i = 0; i < size; i++) {
vec[i].start = intervals[i].start;
vec[i].end = intervals[i].end;
vec[i].idx = i;
}
sort(vec.begin(), vec.end(), comp);
int
max_end = vec[0].end;
int
max_end_idx = 0;
for
(int
i = 0; i < size - 1; i++) {
if
(vec[i].end > max_end) {
max_end = vec[i].end;
max_end_idx = i;
}
if
(max_end >= vec[i+1].start) {
isIntersected[vec[max_end_idx].idx] = true;
isIntersected[vec[i+1].idx] = true;
}
}
} |