My easy AC Java solution use Merge Intervals


  • 0
    H

    We just need to add an interval to intervals and use Merge Intervals, that's OK!

        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            intervals.add(newInterval);
            if (intervals == null || intervals.size() == 1) return intervals;
    
            return merge(intervals);
        }
    
        public List<Interval> merge(List<Interval> intervals) {
            if (intervals == null || intervals.size() < 2) return intervals;
            List<Interval> res = new ArrayList<>();
            int len = intervals.size();
            int[] left = new int[len];
            int[] right = new int[len];
            for (int i = 0; i < len; i++) {
                left[i] = intervals.get(i).start;
                right[i] = intervals.get(i).end;
            }
            Arrays.sort(left);
            Arrays.sort(right);
            for (int i = 0, j = 0; i < len; i++) {
                if (i == len - 1 || left[i + 1] > right[i]) {
                    res.add(new Interval(left[j], right[i]));
                    j = i + 1;
                }
            }
    
            return res;
        }
    

Log in to reply
 

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