[LeetCode#57]Insert Interval

Problem:

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

Wrong solution 1:

The idea behind this problem is really really very easy, but it is really easy to make mistakes when doing the implementation. 
I have made following mistakes, which I thinks I could learn a lot from it!

1. the trigger case of adding interval!!!
I treat the interval.start > newInterval.end as trigger case for add new interval. What iff there is no such case.
Example: [[1,3]] [[2, 5]]
No trigger case!!!
Lesssion: if you use a trigger condition, you should always ask yourself: if such trigger case must exist. This is especially imprtant when the last case does not meet it. 


public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (intervals == null || newInterval == null)
            throw new IllegalArgumentException("the passed in arguments is invalid!");
        List<Interval> ret = new ArrayList<Interval> ();
        if (intervals.size() == 0) {
            ret.add(newInterval);
            return ret;
        }
        for (Interval interval : intervals) {
            if (interval.end < newInterval.start) {
                ret.add(interval);
            } else if (interval.start > newInterval.end) {
                ret.add(newInterval);
                ret.add(interval);
            }
            newInterval.start = Math.min(newInterval.start, interval.start);
            newInterval.end = Math.max(newInterval.end, interval.end);
        }
        return ret;
}


Input:
[[1,5]], [2,3]
Output:
[]
Expected:
[[1,5]]

Wrong solution 2:

2. lack the proper 'return/continue' sentence for a brach, thus result in extra boiling activities.
if (interval.end < newInterval.start) {
    ret.add(interval);
} else if (interval.start > newInterval.end) {
    ret.add(newInterval);
    ret.add(interval);
}
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);

All branch would excute:
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);

Fix method:
1. add continue.
2. never make codes outside branch. the newIntrval.start should be encapsulate in a else block.

if (interval.end < newInterval.start) {
    ret.add(interval);
} else if (interval.start > newInterval.end) {
    ret.add(newInterval);
    ret.add(interval);
} else {
    newInterval.start = Math.min(newInterval.start, interval.start);
    newInterval.end = Math.max(newInterval.end, interval.end);
}

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (intervals == null || newInterval == null)
            throw new IllegalArgumentException("the passed in arguments is invalid!");
        List<Interval> ret = new ArrayList<Interval> ();
        if (intervals.size() == 0) {
            ret.add(newInterval);
            return ret;
        }
        for (Interval interval : intervals) {
            if (interval.end < newInterval.start) {
                ret.add(interval);
            } else if (interval.start > newInterval.end) {
                ret.add(newInterval);
                ret.add(interval);
            }
            newInterval.start = Math.min(newInterval.start, interval.start);
            newInterval.end = Math.max(newInterval.end, interval.end);
        }
        if (intervals.get(intervals.size() - 1).end <= newInterval.end) {
            ret.add(newInterval);
        }
        return ret;
    }

Input:
[[1,5]], [6,8]
Output:
[[1,5],[1,8]]
Expected:
[[1,5],[6,8]]

Wrong solution 3:

3. forget to isolate the insert "newInterval" action to be exectued only one time. ignore there are many susscive case could incur the same add action.
if (interval.start > newInterval.end) {
    ret.add(newInterval);
    ret.add(interval);
    continue;
}

For all intervals after the current inverval would incur the add action. 



public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (intervals == null || newInterval == null)
            throw new IllegalArgumentException("the passed in arguments is invalid!");
        List<Interval> ret = new ArrayList<Interval> ();
        if (intervals.size() == 0) {
            ret.add(newInterval);
            return ret;
        }
        for (Interval interval : intervals) {
            if (interval.end < newInterval.start) {
                ret.add(interval);
                continue;
            } else if (interval.start > newInterval.end) {
                ret.add(newInterval);
                ret.add(interval);
                continue;
            } else {
                newInterval.start = Math.min(newInterval.start, interval.start);
                newInterval.end = Math.max(newInterval.end, interval.end);
            }
        }
        if (intervals.get(intervals.size() - 1).end <= newInterval.end) {
            ret.add(newInterval);
        }
        return ret;
    }

Input:
[[2,5],[6,7],[8,9]], [0,1]
Output:
[[0,1],[2,5],[0,1],[6,7],[0,1],[8,9]]
Expected:
[[0,1],[2,5],[6,7],[8,9]]


The above code is really ugly and easy to maintain, we should avoid it!!!
The major problem is how to insert the newInterval into the result list without adding code complexity.

We know the adding activity could only happen for following two cases:
1. [new interval]  [interval i]  [interval i+1]
incur the insert through afterward interval.
2. [new interval] is the last interval. 
make the check after the last interval. 
for(Interval interval: intervals){
    ...
}
result.add(newInterval); 

How could we combine above two cases perfectly???
Skill: when the newInterval was inserted, it becomes useless. Since all intervals after it could not be merged with it! Why must we keep on maintain it? And all intervals after it actually share the same properity with it, that is not collide with any Interval. They all needed to be inserted, why do not we take such advantage?
for(Interval interval: intervals){
    if (interval.start > newInterval.end){
        result.add(newInterval);
        newInterval = interval; 
    }
}
result.add(newInterval); 
Note: this skill is super important we want to aovid repeatedlly insert new item(has already been inserted), and keep the code as concise as possible!

Solution:

public class Solution {
     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<Interval>();
        for(Interval interval: intervals){
            if(interval.end < newInterval.start){
                result.add(interval);
            }else if(interval.start > newInterval.end){
                result.add(newInterval);
                newInterval = interval;        
            }else {
                newInterval.start = Math.min(newInterval.start, interval.start);
                newInterval.end = Math.max(newInterval.end, interval.end);
            }
        }
 
        result.add(newInterval); 
        return result;
    }
}

[LeetCode#57]Insert Interval

推荐阅读