leetcode Merge Intervals

  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 }