Insert first and then merge interval


  • 0
    D
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> ans = new ArrayList<Interval>();  
    // using binary search to locate the right place to place the new interval
            int l = 0, r = intervals.size() - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (intervals.get(mid).start > newInterval.start) r = mid - 1;
                else l = mid + 1;
            }
            intervals.add(l, newInterval); // insert
    // merge the overlapped intervals
            int start = intervals.get(0).start, end = intervals.get(0).end;
            for (int i = 1; i < intervals.size(); i++) {
                Interval inter = intervals.get(i);
                if (inter.start > end) {
                    ans.add(new Interval(start, end));
                    start = inter.start;
                    end = inter.end;
                }
                else end = Math.max(end, inter.end);
            }
            ans.add(new Interval(start, end));
            return ans;
        }

Log in to reply
 

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