Insert Interval

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> left;
        vector<Interval> right;

        for(auto &p:intervals){
            if(p.end < newInterval.start)
                left.push_back(p);
            else if(p.start > newInterval.end)
                right.push_back(p);
        }

        int s = newInterval.start;
        int e = newInterval.end;
        if(left.size() + right.size() != intervals.size()){
            s = min(s, intervals[left.size()].start);
            e = max(e, intervals[intervals.size() - right.size() - 1].end);
        }
        Interval middle(s, e);
        left.push_back(middle);
        left.insert(left.end(), right.begin(), right.end());

        return left;
    }