#include <iostream> #include <vector> #include <string> using namespace std; struct Interval { int start; int end; Interval() : start(0), end(0) {} Interval(int s, int e) : start(s), end(e) {} }; class Solution { public: inline int max(int a, int b) { return a > b ? a : b; } void addInte2Vec(vector<Interval> &vec, Interval &inte) { if(vec.size() == 0) vec.push_back(inte); else { Interval &last = vec[vec.size() - 1]; if (last.end < inte.start) { vec.push_back(inte); } else if (last.start <= inte.start) { last.end = max(last.end,inte.end); } } } vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> result; if(intervals.size() == 0) { result.push_back(newInterval); return result; } bool merged = false; if(intervals[0].start <= newInterval.start) { result.push_back(intervals[0]); } else { result.push_back(newInterval); merged = true; } for(int i = 0 ; i < intervals.size() ; ++i) { Interval inte = intervals[i]; if (inte.start < newInterval.start) { addInte2Vec(result,inte); } else { addInte2Vec(result,newInterval); merged = true; addInte2Vec(result,inte); } } if(!merged) addInte2Vec(result,newInterval); return result; } }; int main() { vector<Interval> intervals; intervals.clear(); Interval a(1, 5); Interval b(7, 10); intervals.push_back(a); intervals.push_back(b); Interval in(4, 9); Solution s; s.insert(intervals, in); return 0; }