Monday, March 4, 2013

[LeetCode] Insert Interval

Thought:
Scan the ArrayList-> find the start and end-> deal with the case that newinterval is before the start or after the end-> remove s to e-> insert at s-> get the result

Code:
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int s = -1, e = -1;
        for (int i = 0; i < intervals.size(); i++) {
            if (s == -1 && intervals.get(i).end >= newInterval.start) {
                s = i;
            }
            if (intervals.get(i).start <= newInterval.end) {
                e = i;
            }
        }
        if (s == -1) {
            intervals.add(newInterval);
            return intervals;
        }else if (e == -1) {
            intervals.add(0, newInterval);
            return intervals;
        }      
        int start = Math.min(intervals.get(s).start, newInterval.start);
        int end = Math.max(intervals.get(e).end, newInterval.end);
        intervals.subList(s, e+1).clear();
        if (s < intervals.size()) {
            intervals.add(s, new Interval(start, end));
        }else {
            intervals.add(new Interval(start, end));
        }
        return intervals;
    }
}

No comments:

Post a Comment