BiruLyu
7/26/2017 - 11:01 PM

57. Insert Interval(#).java

/**
 * 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; }
 * }
 */
// if output is total interval time, then array should be sorted to get the time
// if output should be sorted, we may need to sort the array
// if output should be not overlapping, we may need to merge intervals

// input: unsorted, no overlaps; output: can be unsorted, return total time; O(n) time, O(n) space
public class Solution {
    public int insert(List<Interval> intervals, Interval newInterval) {
        if (newInterval == null) {
            return 0;
        }
        int totalTime = 0;
        //if you need to insert intervals while calculating time,add:
        //List<Interval> res = new ArrayList<>();
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start <= newInterval.end || intervals.get(i).end >= newInterval.start) {//merge overlaps
                newInterval.start = Math.min(newInterval.start, intervals.get(i).start);//remember to update the start!!!
                newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            } else {
                totalTime += intervals.get(i).end - intervals.get(i).start;
                //res.add(intervals.get(i));//add all non-overlapping intervals
            }
        }
        totalTime += newInterval.end - newInterval.start;//we add the time of merged newInterval here
        //if you need to insert intervals while calculating time,add:
        //res.add(newInterval);//add the newInterval when all intervals have been checked so that no overlap exists
        return totalTime;
    }
}

// input: unsorted, no overlaps; output: can be unsorted; O(n) time, O(1) space
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (newInterval == null) {
            return intervals;
        
        List<Interval> res = new ArrayList<>();
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start <= newInterval.end || intervals.get(i).end >= newInterval.start) {//merge overlaps
                newInterval.start = Math.min(newInterval.start, intervals.get(i).start);//remember to update the start too!!!
                newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            } else {
                res.add(intervals.get(i));//add all non-overlapping intervals
            }
        }
        res.add(newInterval);//add the newInterval when all intervals have been checked so that no overlap exists
        return res;
    }
}

// input: sorted, no overlaps; output should be sorted; O(n) time, O(1) space
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (newInterval == null) {
            return intervals;
        }
        // if the input is unsorted, add: (which will make this algo O(nlogn) time)
        // Collections.sort(intervals, new Comparator<Interval>(){
        //     public int compare(Interval a, Interval b) {
        //         return a.start - b.start;
        //     }
        // });
        List<Interval> res = new ArrayList<>();
        int i = 0;
        while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
            res.add(intervals.get(i++));//add all intervals before the insert position of the new interval
        }//then we try to merge all intervals that can be merged
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {//not intervals.get(i).end>=newInterval.end
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);//remember to update the start !!!
            newInterval.end = Math.max(newInterval.end, intervals.get(i++).end);
        }
        res.add(newInterval);//add the newInterval when no overlap exists
        while (i < intervals.size()) {
            res.add(intervals.get(i++));//add the rest of the non overlapping intervals
        }
        return res;
    }
}
/**
 * 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 List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null) return res;
        int len = intervals.size();
        int i = 0;
        while (i < len && intervals.get(i).end < newInterval.start) {
            res.add(intervals.get(i++));
        }
        while (i < len && intervals.get(i).start <= newInterval.end ) {
            newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
            newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
            i++;
        }
        res.add(newInterval);
        while (i < len) {
            res.add(intervals.get(i++));
        }
        return res;
    }
}