/** * 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 ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { ArrayList<Interval> result = new ArrayList<>();
int left = 0; int right = intervals.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (newInterval.start <= intervals.get(mid).end) { right = mid; } else { left = mid + 1; } } int p = left;
result.addAll(intervals.subList(0, p)); for (int i = p; i < intervals.size(); i++) { Interval curr = intervals.get(i); if (newInterval.end < curr.start) { result.add(newInterval); newInterval = curr; } else if (curr.end < newInterval.start) { result.add(curr); } else { newInterval = new Interval(Math.min(curr.start, newInterval.start), Math.max(curr.end, newInterval.end)); } } result.add(newInterval); return result; } }