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].

• Time: O(n)
• Space: O(1)

public List<Interval> insert(List<Interval> intervals, Interval newInt) {
    List<Interval> ret = new ArrayList<>();
    boolean flag = false;
    for (int i = 0; i < intervals.size(); i++) {
        Interval cur = intervals.get(i);
        if (flag || cur.end < newInt.start) {
            ret.add(cur);
        } else if (cur.start > newInt.end) {
            ret.add(newInt);
            ret.add(cur);
            flag = true;
        } else {
            newInt.start = Math.min(cur.start, newInt.start);
            newInt.end = Math.max(cur.end, newInt.end);
        }
    }
    if (!flag) {
        ret.add(newInt);
    }
    return ret;
}