InsertInterval { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { List<Interval> result = new ArrayList<>(intervals); Comparator<Interval> comp = Comparator.comparing((Interval i) -> i.start). thenComparing((Interval i) -> i.end); Collections.sort(result, comp); int[] starts = result.stream().mapToInt(i -> i.start).toArray(); int iStart = Arrays.binarySearch(starts, newInterval.start); int iEnd = Arrays.binarySearch(starts, newInterval.end); int is = iStart < 0 ? -iStart - 1 : iStart; int ie = iEnd < 0 ? -iEnd - 1 : iEnd; if (is == ie && iStart >= 0 && iEnd >= 0) { return intervals; } while (is > 0 && result.get(is - 1).end >= newInterval.start) { is--; } while (ie < result.size() && result.get(ie).start <= newInterval.end) { ie++; } int s, e; if (is == ie) { s = newInterval.start; e = newInterval.end; } else { s = Math.min(result.get(is).start, newInterval.start); e = Math.max(newInterval.end, result.get(ie - 1).end); } for (int i = ie - 1; i >= is; i--) { result.remove(i); } result.add(is, new Interval(s, e)); return result; }  List<Interval> insert(List<Interval> intervals, Interval newInterval);  }
@Test(dataProvider = "intervals") public void testInsert(List<Interval> intervals, Interval newInterval, List<Interval> expected) { assertEquals(new InsertInterval().insert(intervals, newInterval), expected); }