3ms Java Solution


  • 0
    L
    /**
     * 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) {
            
            // 如果intervals是空的,或者长度为0
            if(intervals == null) return new ArrayList<>();
            if(intervals.size() == 0){
                if(newInterval != null){
                    intervals.add(newInterval);
                }
                return intervals;
            }
            
            
            
            int startIndex = 0;
            while(startIndex < intervals.size()){
                Interval currInterval = intervals.get(startIndex);
                
                // 找到第一个满足 newInterval.start <= currInterval.end 的条件的currInterval
                if(newInterval.start <= currInterval.end){
                    // 如果这个newInterval在currInterval之前不用merge的位置
                    if(newInterval.end < currInterval.start){
                        intervals.add(startIndex, newInterval);
                        return intervals;
                    }else{
                        // 否则更新这个interval的start
                        currInterval.start = Math.min(currInterval.start, newInterval.start);
                        
                    }
                    break;
                }
                startIndex++;
            }
            
            // 如果start == intervals.size()的话,直接插入最后并返回
            if(startIndex == intervals.size()){
                intervals.add(newInterval);
                return intervals;
            }
            
            // 开始找结束的位置
            int endIndex = startIndex;
            
            while(endIndex < intervals.size()){
                Interval currInterval = intervals.get(endIndex);
                if(newInterval.end < currInterval.start){
                    // 找到的其实是endIndex + 1, 所以要--
                    break;
                }
                endIndex++;
            }
            
            // 如果没找到
            // endIndex = intervals.size(), 只需merge掉最后一个就好
            // 如果找到了,找到的endIndex是最后一个的下一个,所以还是用同样的方法merge
            endIndex--;
            intervals.get(endIndex).end = Math.max(intervals.get(endIndex).end, newInterval.end);
    
            
            // 如果找到start和endIndex一样的话,已经都merge过了,可以直接返回
            if(startIndex == endIndex) return intervals;
            
            
            // 否则建立一个新的arrayList来进行放入原来的所有元素
            List<Interval> retList = new ArrayList<>();
            
            newInterval.start = intervals.get(startIndex).start;
            newInterval.end = intervals.get(endIndex).end;
            
            for(int i = 0; i < startIndex; i++){
                retList.add(intervals.get(i));
            }
            
            retList.add(newInterval);
            
            for(int i = endIndex + 1; i < intervals.size(); i++){
                retList.add(intervals.get(i));
            }
            
            return retList;
        }
    }

Log in to reply
 

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