Dummy and verbose solution. But I think this problem throws out some technics to learn

• So my solution is find the first interval with end less or equal than new one's start and last interval with start greater or equal than new one's end. I know this is pretty dummy comparing to those top posts, but I think it combines 2 binary search questions: find first and find last. Best running time would be better than linear search method, which is O(logn) while the worst is still O(N). Good for practicing.

/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<>();
if (intervals == null || intervals.isEmpty()) {
return result;
}
int start = findLastLessEqualThanStart(intervals, newInterval);
int end = findFirstGreaterEqualThanEnd(intervals, newInterval);
if (start == -1 && end == -1) {
} else if (start == -1) {
if (intervals.get(end).start <= newInterval.end) {
newInterval.end = intervals.get(end).end;
end += 1;
}
for (int i = end; i < intervals.size(); i++) {
}
} else if (end == -1) {
if (intervals.get(start).end >= newInterval.start) {
newInterval.start = intervals.get(start).start;
start -= 1;
}
for (int i = 0; i <= start; i++) {
}
} else {
if (intervals.get(start).end >= newInterval.start) {
newInterval.start = intervals.get(start).start;
start -= 1;
}
if (intervals.get(end).start <= newInterval.end) {
newInterval.end = intervals.get(end).end;
end += 1;
}
for (int i = 0; i <= start; i++) {
}
for (int i = end; i < intervals.size(); i++) {
}
}
return result;
}

int findLastLessEqualThanStart(List<Interval> intervals, Interval newInterval) {
int i = 0, j = intervals.size() - 1;
while (i + 1 < j) {
int mid = i + (j - i) / 2;
int midStart = intervals.get(mid).start;
if (newInterval.start > midStart) {
i = mid;
} else if (newInterval.start < midStart) {
j = mid - 1;
} else {
return mid;
}
}
if (intervals.get(j).start <= newInterval.start) {
return j;
} else if (intervals.get(i).start <= newInterval.start) {
return i;
} else {
return -1;
}
}

int findFirstGreaterEqualThanEnd(List<Interval> intervals, Interval newInterval) {
int i = 0, j = intervals.size() - 1;
while (i + 1 < j) {
int mid = i + (j - i) / 2;
int midEnd = intervals.get(mid).end;
if (newInterval.end < midEnd) {
j = mid;
} else if (newInterval.end > midEnd) {
i = mid + 1;
} else {
return mid;
}
}
if (intervals.get(i).end >= newInterval.end) {
return i;
} else if (intervals.get(j).end >= newInterval.end) {
return j;
} else {
return -1;
}
}
}

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