Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Solution:
1. /*
2. * Definition for an interval.
3. * public class Interval {
4. * int start;
5. * int end;
6. * Interval() { start = 0; end = 0; }
7. * Interval(int s, int e) { start = s; end = e; }
8. * }
9. /
10. public class Solution {
11. public List insert(List intervals, Interval newInterval) {
12. List res = new ArrayList<>();
13. 14. int i = 0, n = intervals.size();
15. 16. while (i < n && intervals.get(i).end < newInterval.start) {
17. res.add(intervals.get(i++));
18. }
19. 20. while (i < n && intervals.get(i).start <= newInterval.end) {
21. newInterval = new Interval(
22. Math.min(newInterval.start, intervals.get(i).start),
23. Math.max(newInterval.end, intervals.get(i).end)
24. );
25. i++;
26. }
27. 28. res.add(newInterval);
29. 30. while (i < n) {
31. res.add(intervals.get(i++));
32. }
33. 34. return res;
35. }
36. }