Java binary search solution

• The input intervals are not overlapping, thus the start times and end times are both sorted, then binary search can be applied to locate the overlapping area in O(lgN).

The best case time complexity is O(lgN), and the worst case is still O(N) for the insertion.

``````public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
int startIdx = Collections.binarySearch(intervals, new Interval(0, newInterval.start), new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.end - o2.end;
}
});

if (startIdx < 0 ) startIdx = -startIdx - 1;

if (startIdx == intervals.size()) {
return intervals;
}

List<Interval> res = new ArrayList<>();
for (int i = 0; i < startIdx; i++) {
}

int endIdx = Collections.binarySearch(intervals, new Interval(newInterval.end, 0), new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});

if (endIdx < 0) {
endIdx = -endIdx - 1 - 1;
}

if (endIdx < startIdx) {
} else {
int left = Math.min(newInterval.start, intervals.get(startIdx).start);
int right = Math.max(newInterval.end, intervals.get(endIdx).end);
}
for (int i = endIdx + 1; i < intervals.size(); i++) {
}
return res;
}
}
``````

• The better version

``````class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<>();
Interval key = new Interval(newInterval.end, newInterval.start);
int l = Collections.binarySearch(intervals, key, (a, b) -> a.end - b.end);
if (l < 0) l = -l - 1;
int r = Collections.binarySearch(intervals, key, (a, b) -> a.start - b.start);
if (r < 0) r = -r - 2;
int i = 0;