Posted on 2014-01-20 22:40
Uriel 阅读(198)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
合并区间，算是经典题了吧，所有区间头尾打乱排序（值相同时区间头排前面！），然后用一个变量记录当前有几重重叠区间，从0->1是为一个合并后的新区间的起始，1->0时为一个合并后的新区间的结束，CE若干次，因为不熟C++，cmp函数写在class里面，WA一次，排序没考虑值相同的情况。。
1 /**
2 * Definition for an interval.
3 * struct Interval {
4 * int start;
5 * int end;
6 * Interval() : start(0), end(0) {}
7 * Interval(int s, int e) : start(s), end(e) {}
8 * };
9 */
10
11 struct seg {
12 int fg; //0->start
13 int val;
14 };
15
16 bool cmp(seg a, seg b) {
17 if(a.val != b.val) return a.val < b.val;
18 return a.fg < b.fg;
19 }
20
21 class Solution {
22 public:
23 seg s[100010];
24 vector<Interval> merge(vector<Interval> &intervals) {
25 int n = 0;
26 vector<Interval> res;
27 Interval tp;
28 if(!intervals.size()) return res;
29 for(int i = 0; i < intervals.size(); ++i) {
30 s[n].val = intervals[i].start;
31 s[n].fg = 0;
32 ++n;
33 s[n].val = intervals[i].end;
34 s[n].fg = 1;
35 ++n;
36 }
37 sort(s, s + n, cmp);
38 int nt = 0;
39 for(int i = 0; i < n; ++i) {
40 if(!s[i].fg) {
41 nt++;
42 if(nt == 1) tp.start = s[i].val;
43 }
44 else {
45 nt--;
46 if(!nt) {
47 tp.end = s[i].val;
48 res.push_back(tp);
49 }
50 }
51 }
52 return res;
53 }
54 };