本文主要是介绍[leetcode hot150]第五十七题，插入区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 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()][]);}
}
这篇关于[leetcode hot150]第五十七题，插入区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
