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

Solution:

We use binary search to find the place where to insert the element such that all the elements are sorted according to their start times. Then we have to see if we have to merge with the previous one and with all the following ones.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) 
    {
        int position = findPosition(intervals, newInterval, 0, intervals.size()-1);
        if(position > 0 && intervals.get(position-1).end >= newInterval.start)
        {
            intervals.get(position-1).end = Math.max(intervals.get(position-1).end, newInterval.end);
            position--;
        }
        else
            intervals.add(position, newInterval);
        while (position < intervals.size()-1 && intervals.get(position).end >= intervals.get(position+1).start)
        {
            intervals.get(position).end =   Math.max(intervals.get(position).end, intervals.get(position+1).end);
            intervals.remove(position+1);
        }
        return intervals;
        
    }
    
    private int findPosition(ArrayList<Interval> intervals, Interval target, int start, int end)
    {
        if (end < start)
            return start;
        int midpoint= (start+end) /2;
        if (intervals.get(midpoint).start <= target.start)
            return findPosition(intervals, target, midpoint+1, end);
        return findPosition(intervals, target, start, midpoint-1);
    }
}