O(n) Solution for Java,


  • 0
    D

    class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> l = new ArrayList<>();
    boolean inser = true;// judge where to insert the newInterval;
    for(int i = 0; i<intervals.size(); i++){// if the newInterval is overloaping, merge it, until there is no overloap with newInterval;
    if((intervals.get(i).start<= newInterval.start && intervals.get(i).end>=newInterval.start ) ||
    (newInterval.start <=intervals.get(i).start && newInterval.end>=intervals.get(i).start )){
    newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
    newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
    intervals.remove(i);
    i--;
    continue;
    }
    if(newInterval.start<intervals.get(i).start && inser == true){ //move the intervals to l;
    l.add(newInterval);
    l.add(intervals.get(i));
    inser = false;
    }else{ l.add(intervals.get(i)); }
    }
    if(inser == true){ l.add(newInterval); }// if the newInterval is the last one, you need to add it;
    return l;
    }

    }


Log in to reply
 

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