题目:
给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals
,其中 intervals[i] = [starti, endi]
表示第 i
个区间的开始和结束,并且 intervals
按照 starti
升序排列。同样给定一个区间 newInterval = [start, end]
表示另一个区间的开始和结束。
在 intervals
中插入区间 newInterval
,使得 intervals
依然按照 starti
升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。
返回插入之后的 intervals
。
注意 你不需要原地修改 intervals
。你可以创建一个新数组然后返回它。
遍历
intervals
列表,将不与newInterval
重叠的区间直接加入结果列表。对于与newInterval
重叠的区间,需要合并它们。具体步骤如下:
- 初始化一个空列表
result
用于存储最终结果。- 遍历
intervals
,对于每个区间interval
:
- 如果
interval
在newInterval
的左侧,不重叠,直接将interval
加入result
。- 如果
interval
与newInterval
重叠,更新newInterval
的起始端点和结束端点,使其覆盖重叠的区间。- 如果
interval
在newInterval
的右侧,不重叠,将newInterval
加入result
,然后将interval
加入result
。- 如果在遍历过程中没有将
newInterval
加入result
,说明newInterval
在所有区间的右侧,将其加入result
。- 返回
result
。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class no_57 {public static void main(String[] args) {int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};int[] newInterval = {4, 8};int[][] re = insert(intervals, newInterval);for (int[] arr : re) {System.out.println(Arrays.toString(arr));}}public static int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> result = new ArrayList<>();int i = 0;int n = intervals.length;while (i < n && intervals[i][1] < newInterval[0]) {result.add(intervals[i]);i++;}while (i < n && intervals[i][0] <= newInterval[1]) {newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}result.add(newInterval);while (i < n) {result.add(intervals[i]);i++;}return result.toArray(new int[result.size()][]);}
}