1 /*****************************************************************  2 created:    2014/09/13 21:32  3 filename:    merge-intervals.cpp  4 author:        Justme0 (http://blog.csdn.net/justme0)  5   6 purpose:    合并交叉的区间  7 https://oj.leetcode.com/problems/merge-intervals/  8 *****************************************************************/  9  10 #define _CRT_SECURE_NO_WARNINGS 11 #include <iostream> 12 #include <vector> 13 #include <algorithm> 14 #include <cassert> 15 using namespace std; 16  17 struct Interval { 18     int start; 19     int end; 20  21     Interval() : start(0), end(0) {} 22     Interval(int s, int e) : start(s), end(e) {} 23 }; 24  25 /** 26  * Definition for an interval. 27  * struct Interval { 28  *     int start; 29  *     int end; 30  *     Interval() : start(0), end(0) {} 31  *     Interval(int s, int e) : start(s), end(e) {} 32  * }; 33  */ 34 class Solution { 35 public: 36     vector<Interval> merge(vector<Interval> &intervals) { 37         if (intervals.empty()) { 38             return vector<Interval>(); 39         } 40  41         vector<Point> coordinates; 42         for (auto iter = intervals.begin(); iter != intervals.end(); ++iter) { 43             coordinates.push_back(Point(iter->start, true)); 44             coordinates.push_back(Point(iter->end, false)); 45         } 46         sort(coordinates.begin(), coordinates.end(), cmp); 47  48         int depth = 0;    // 覆盖的深度 49         assert(coordinates.front().isLeft); 50         vector<Interval> merged_itvs; 51         int start = 0; 52         for (auto iter = coordinates.begin(); iter != coordinates.end(); ++iter) { 53             assert(depth >= 0); 54             if (0 == depth) { 55                 start = iter->x;    // 此时“栈空”，iter 指向左端点，开始合并一个区间 56             } 57             iter->isLeft ? ++depth : --depth; 58             if (0 == depth) { 59                 merged_itvs.push_back(Interval(start, iter->x));    // 此时“栈空”，iter 指向右端点，确定了一个区间 60             } 61         } 62  63         return merged_itvs;        // 接口设计得不好 64     } 65  66     struct Point { 67         int x; 68         bool isLeft; 69  70         Point() : x(0), isLeft(false) {} 71  72         Point(int _x, bool _isLeft) : x(_x), isLeft(_isLeft) {} 73  74 //         bool operator<(const Point &other) const { 75 //             if (this->x < other.x) { 76 //                 return true; 77 //             } else if (this->x > other.x) { 78 //                 return false; 79 //             } else if (this->isLeft == other.isLeft) { 80 //                 return this < &other; 81 //             } else { 82 //                 return this->isLeft; 83 //             } 84 //         } 85     }; 86  87     static bool cmp(const Point &a, const Point &b) { 88         if (a.x < b.x) { 89             return true; 90         } else if (a.x > b.x) { 91             return false; 92         } else if (a.isLeft == b.isLeft) { 93             return false; 94         } else { 95             return a.isLeft; 96         } 97     } 98  99 };100 101 int main(int argc, char **argv) {102     freopen("cin.txt", "r", stdin);103 104     vector<Interval> vec;105     int a, b;106     while (cin >> a >> b) {107         vec.push_back(Interval(a, b));108     }109 110     vector<Interval> ans = Solution().merge(vec);111     for (auto ite = ans.begin(); ite != ans.end(); ++ite) {112         cout << ite->start << ‘ ‘ << ite->end << endl;113     }114 115     system("PAUSE");116     return 0;117 }