A straight forward but cumbersome solution with O(n*lgn) complexity, please help to modify


  • 0
    L
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        if(intervals.size() == 0) {
            result.add(newInterval);
            return result;
        }
        int n = intervals.size();
        int start = Integer.MAX_VALUE;
        int end = Integer.MIN_VALUE;
        for(Interval interval : intervals) {
            if(interval.end < newInterval.start || interval.start > newInterval.end) result.add(interval);
            else {
                start = Math.min(start, Math.min(interval.start, newInterval.start));
                end = Math.max(end, Math.max(interval.end, newInterval.end));
            }
        }
        start = Math.min(start, newInterval.start);
        end = Math.max(end, newInterval.end);
        result.add(new Interval(start, end));
        
        Collections.sort(result, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);
            }
        });
        
        return result;
    }

Log in to reply
 

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