Java Solution with half binary search, short clean code


  • 0
    L

    I first added a fake tail at the end, so that i can merge some cases when finding the start index and end index.
    I use binary search to find the first start index.
    Then I iterate from start to find the end instead of using binary search to find the end index, since when we merge the lists, we need to go through that part of list.
    I didn't call remove in the while loop, and I used s.sublist(i, j).clear() which will only call one copy() while remove() calls one each time you remove.

    Here is the code:

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    	int front = newInterval.start;
    	int back = newInterval.end;
    	if (intervals.size() == 0 || back < intervals.get(0).start) {
    	       intervals.add(0, newInterval);
    	        return intervals;
    	}
            intervals.add(new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE));
            
            int start = binarySearch (0, intervals.size() - 1, front, intervals);
            int i = start;
    	while (intervals.get(i).start <= back) {
    		i ++;
    	}
    	int min = Math.min(front, intervals.get(start).start);
    	int max = Math.max(back, intervals.get(i- 1).end);
    	intervals.subList(start, i).clear();
    	intervals.add(start, new Interval(min, max));
    	intervals.remove(intervals.size() - 1);
    	return intervals;
        }
    	
    	private int binarySearch (int start, int end, int front, List<Interval> intervals) {
    		while (start <= end) {
    			int mid = start + (end - start) / 2;
    			int endValue = intervals.get(mid).end;
    			if (endValue == front || endValue > front && intervals.get(mid).start <= front) {
    				return mid;
    			} else if (endValue > front) {
    				end = mid - 1;
    			} else {
    				start = mid + 1;
    			}
    		}
    		return start;
    	}
    
    

Log in to reply
 

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