[LeetCode]Insert Interval

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (newInterval == null)
            return intervals;
        if (intervals.size() == 0) intervals.add(newInterval);
        List<Interval> rsIntervals = new LinkedList<Interval>();
        if (intervals == null) {
            rsIntervals.add(newInterval);
        } else {
            int start = newInterval.start;
            int end = newInterval.end;
            Interval interval = null;
            for (int i = 0; i < intervals.size(); ++i) {
                interval = intervals.get(i);
                if (start <= interval.end) {
                    Interval in = new Interval();
                    if (start < interval.start) {
                        in.start = start;//起始
                    } else {
                        in.start = interval.start;
                    }
                    i = getEndANDNextInterval(intervals, rsIntervals, newInterval.end, i, in);
                    while (i < intervals.size()) {
                        rsIntervals.add(intervals.get(i));
                        i++;
                    }
                    return rsIntervals;
                } else {
                    rsIntervals.add(interval);
                    if (i + 1 >= intervals.size()) {
                        rsIntervals.add(newInterval);
                    }
                }
            }


        }
        return rsIntervals;

    }

    /**
     * @param intervals
     * @param end
     * @param istart
     * @param interval
     * @return
     */
    public int getEndANDNextInterval(List<Interval> intervals, List<Interval> rsIntervals, int end, int istart, Interval interval) {
        int index = 0;
        Interval in = null;
        for (int i = istart; i < intervals.size(); ++i) {
            in = intervals.get(i);
            if (end < in.start) {
                interval.end = end;
                rsIntervals.add(interval);
                return i;
            }
            if (end <= in.end) {
                interval.end = in.end;
                rsIntervals.add(interval);
                return i + 1;
            } else {
                i++;
                while (i < intervals.size()) {
                    in = intervals.get(i);
                    if (end < in.start) {
                        interval.end = end;
                        rsIntervals.add(interval);
                        return i;
                    } else if (end <= in.end) {
                        interval.end = in.end;
                        rsIntervals.add(interval);
                        return i + 1;
                    }
                    i++;
                }
                interval.end = end;//全包涵后面的元素
                rsIntervals.add(interval);
                return i;
            }
        }
        return index;
    }

public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        if (newInterval == null || intervals == null) {
            return intervals;
        }

        ArrayList<Interval> results = new ArrayList<Interval>();
        int insertPos = 0;

        for (Interval interval : intervals) {
            if (interval.end < newInterval.start) {
                results.add(interval);
                insertPos++;
            } else if (interval.start > newInterval.end) {
                results.add(interval);
            } else {
                newInterval.start = Math.min(interval.start, newInterval.start);
                newInterval.end = Math.max(interval.end, newInterval.end);
            }
        }

        results.add(insertPos, newInterval);

        return results;
    }
}

[LeetCode]Insert Interval

原文：http://blog.csdn.net/youmengjiuzhuiba/article/details/44625289