Leetcode Insert Interval problem solution

In this Leetcode Insert Interval problem solution, we have 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.

Problem solution in Python.

class Solution(object):
    def insert(self, intervals, newInterval):
        # O(n)
        left, right, s, e = [], [], newInterval.start, newInterval.end
        for i in intervals:
            if i.end < s: left.append(i)
            elif i.start > e: right.append(i)
            else: s, e = min(s, i.start), max(e, i.end)
        return left + [Interval(s, e)] + right
        
        # O(nlogn)
        res = []
        for i in sorted(intervals + [newInterval], key = lambda x: x.start):
            if not res: res.append(i)
            else:
                if i.start <= res[-1].end: res[-1].end = max(res[-1].end, i.end)
                else: res.append(i)
        return res

Problem solution in Java.

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> ans = new ArrayList<>();
    int i = 0, start = 0, end = 0;
    for (Interval e : intervals) {
        if (e.end < newInterval.start)
            ans.add(e);
        else if (end == 0 && e.end >= newInterval.start){ 
            if (e.start > newInterval.end) {
                ans.add(newInterval);
                ans.add(e);
                end = 1; start = 1;
            } else { 
                newInterval.start = Math.min(e.start, newInterval.start);
                newInterval.end = Math.max(e.end, newInterval.end);
                end = 1;
            }       
        } else if (start == 0 && e.start <= newInterval.end) { 
            newInterval.end = Math.max(e.end, newInterval.end);
        } else {
            if (start == 0) {
                ans.add(newInterval);
                start = 1;
            }
            ans.add(e);
        }
    }
    if (end == 0 || start == 0) {
        ans.add(newInterval);
        return ans;
    }          
    return ans;
}

Problem solution in C++.

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval t) {
        vector<Interval> result; 
        int i=0;
        bool t_added=false;
        for(i=0; i<intervals.size(); ++i) {
            if(intervals[i].end<t.start)
                result.push_back(intervals[i]);
            else if(intervals[i].start > t.end){
                result.push_back(t);
                t_added=true;
                break;
            }
            else {
                t.start=min(t.start, intervals[i].start);
                t.end=max(t.end, intervals[i].end);
            }
        }
        if(!t_added) result.push_back(t);
        for(; i<intervals.size(); ++i){
            result.push_back(intervals[i]);
        }
        return result;
    }
};

coding problems