Posted on 2014-01-20 22:40
Uriel 閱讀(220)
評論(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 };