package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by gouthamvidyapradhan on 15/12/2017.
 * 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: O(n): Iterate through each interval and check for each overlapping case
 */
public class InsertInterval {

    public static class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        Interval i1 = new Interval(1, 2);
        Interval i2 = new Interval(3, 5);
        Interval i3 = new Interval(6, 7);
        Interval i4 = new Interval(8, 10);
        Interval i5 = new Interval(12, 16);
        List<Interval> list = Arrays.asList(i1, i2, i3, i4, i5);
        List<Interval> result = new InsertInterval().insert(list, new Interval(2, 5));
        result.stream().map(x -> x.start + " " + x.end).forEach(System.out::println);
    }

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        for(int i = 0, l = intervals.size(); i < l; i ++){
            Interval curr = intervals.get(i);
            if(newInterval.start >= curr.start && newInterval.end <= curr.end){
                insertRest(intervals, result, i);
                return result; //easy case
            } else if(newInterval.start < curr.start && newInterval.end > curr.end){
                newInterval = new Interval(newInterval.start, newInterval.end);
                //merge and continue
            } else if(newInterval.start >= curr.start && newInterval.start <= curr.end
                    && newInterval.end > curr.end){
                newInterval = new Interval(curr.start, newInterval.end);
                //merge and continue
            } else if(newInterval.start < curr.start && newInterval.end >= curr.start
                    && newInterval.end <= curr.end){
                Interval newI = new Interval(newInterval.start, curr.end);
                result.add(newI);
                insertRest(intervals, result, i + 1);
                return result;
            } else if(newInterval.start > curr.end){
                result.add(curr);
            } else {
                result.add(newInterval);
                insertRest(intervals, result, i);
                return result;
            }
        }
        result.add(newInterval);
        return result;
    }

    private void insertRest(List<Interval> intervals, List<Interval> result, int i){
        int l = intervals.size();
        while(i < l){
            result.add(intervals.get(i));
            i++;
        }
    }

}