AC O(n) JAVA solution


  • 0
    W
    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> res = new LinkedList<Interval>();
            int indexToInsert = intervals.size();
            for (int i = 0; i < intervals.size(); i++) {
                if (intervals.get(i).end < newInterval.start) {
                    res.add(intervals.get(i));
                } else {
                    newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
                    indexToInsert = i;
                    break;
                }
            }
            for (int i = intervals.size() - 1; i >= 0; i--) {
                if (intervals.get(i).start > newInterval.end) {
                    res.add(indexToInsert, intervals.get(i));
                } else {
                    newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
                    break;
                }
            }
            res.add(indexToInsert, newInterval);
            return res;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.