Concise solution using stl
use lower_bound find the left and right bound of newinterval, step back or forward if need.\n\n\n    bool comp1(const Interval& lhs ,const Interval& rhs)\n\t{\n
use lower_bound find the left and right bound of newinterval, step back or forward if need.\n\n\n    bool comp1(const Interval& lhs ,const Interval& rhs)\n\t{\n\t\treturn lhs.start < rhs.start;\n\t}\n\tbool comp2(const Interval& lhs ,const Interval& rhs)\n\t{\n\t\treturn lhs.end < rhs.end;\n\t}\n\n\tvector<Interval> insert(vector<Interval> &intervals, Interval newInterval) \n\t{\n\t\tvector<Interval>::iterator begin = lower_bound(intervals.begin(), intervals.end(), newInterval, comp1);\n\t\tif(begin != intervals.begin() && (begin - 1)->end >= newInterval.start)\n\t\t{\n\t\t\t--begin;\n\t\t\tnewInterval.start = begin->start;\n\t\t}\n\n\t\tvector<Interval>::iterator end = lower_bound(intervals.begin(), intervals.end(), newInterval, comp2);\t\t\n\t\tif(end != intervals.end() && end->start <= newInterval.end)\n\t\t{\n\t\t\tnewInterval.end = end->end;\n\t\t\t++end;\t\t\t\n\t\t}\n\t\tvector<Interval>::iterator t = intervals.erase(begin, end);\n\t\tintervals.insert(t, newInterval);\n\n\t\treturn intervals;\n\t}
[]