Leetcode 57: insert interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

insert interval和 merge interval解法类似，先要找到insert的位置，然后再对newinterval以及newinterval后面的interval进行合并。但是要注意如果insert的位置是第一个位置，就没有前面需要insert的，此时直接将newinterval插入结果集合。时间复杂度：O(n)

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> rst;
        //sanity check
        if (intervals.size() == 0) {
            rst.push_back(newInterval);
            return rst;
        }
        int i = 0;
        for (i = 0; i < intervals.size(); i++) {
            if (intervals[i].start >= newInterval.start) { //find the position to insert
                break;
            } else {
                rst.push_back(intervals[i]);
            }
        }
        if (i == 0) { //insert new interval to the head
            rst.push_back(newInterval);
        }else if (rst[rst.size()-1].end >= newInterval.start) {
            rst[rst.size()-1].end = max(rst[rst.size()-1].end, newInterval.end);
        } else {
            rst.push_back(newInterval);
        }
        for (; i <  intervals.size(); i++) {
            if (rst[rst.size()-1].end >= intervals[i].start) {
                rst[rst.size()-1].end = max(rst[rst.size()-1].end, intervals[i].end);
            } else {
                rst.push_back(intervals[i]);
            }
        }
        return rst;
    }
};