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; } }} |
原文：http://www.cnblogs.com/lautsie/p/3522922.html