整数数组区间的插入与删除

相似题参考：

56. Merge Intervals - 力扣（LeetCode）合并区间

57. 插入区间 - 力扣（LeetCode）

1272. 删除区间

package Jerry;import org.junit.Assert;
import org.junit.Test;import java.util.ArrayList;
import java.util.List;// Task: Implement a class named 'RangeList'
// A pair of integers define a range, for example: [1, 5). This range includes integers: 1, 2, 3, and 4.
// A range list is an aggregate of these ranges: [1, 5), [10, 11), [100, 201)public class RangeList {// 结果private List<int[]> intervals = new ArrayList<>();// toString 使用的静态常量private static final String LEFT = "[";private static final String RIGHT = ")";private static final String FLAG = ", ";private static final String BLANK = " ";/*** junit单元测试*/@Testpublic void test() {RangeList rl = new RangeList();System.out.println(rl.toString()); // Should be ""Assert.assertEquals(rl.toString(), "");rl.add(1, 5);//rl.add(new int[]{1, 5});System.out.println(rl.toString()); // Should be: "[1, 5)"Assert.assertEquals(rl.toString(), "[1, 5)");rl.add(10, 20);System.out.println(rl.toString()); // Should be: "[1, 5) [10, 20)"Assert.assertEquals(rl.toString(), "[1, 5) [10, 20)");rl.add(20, 20);System.out.println(rl.toString()); // Should be: "[1, 5) [10, 20)"Assert.assertEquals(rl.toString(), "[1, 5) [10, 20)");rl.add(20, 21);System.out.println(rl.toString()); // Should be: "[1, 5) [10, 21)"Assert.assertEquals(rl.toString(), "[1, 5) [10, 21)");rl.add(2, 4);System.out.println(rl.toString()); // Should be: "[1, 5) [10, 21)"Assert.assertEquals(rl.toString(), "[1, 5) [10, 21)");rl.add(3, 8);System.out.println(rl.toString()); // Should be: "[1, 8) [10, 21)"Assert.assertEquals(rl.toString(), "[1, 8) [10, 21)");rl.remove(10, 10);System.out.println(rl.toString()); // Should be: "[1, 8) [10, 21)"Assert.assertEquals(rl.toString(), "[1, 8) [10, 21)");rl.remove(10, 11);System.out.println(rl.toString()); // Should be: "[1, 8) [11, 21)"Assert.assertEquals(rl.toString(), "[1, 8) [11, 21)");rl.remove(15, 17);System.out.println(rl.toString()); // Should be: "[1, 8) [11, 15) [17, 21)"Assert.assertEquals(rl.toString(), "[1, 8) [11, 15) [17, 21)");rl.remove(3, 19);System.out.println(rl.toString()); // Should be: "[1, 3) [19, 21)"Assert.assertEquals(rl.toString(), "[1, 3) [19, 21)");// 新增移除区间不存在的情况rl.remove(4, 18);System.out.println(rl.toString()); // Should be: "[1, 3) [19, 21)"Assert.assertEquals(rl.toString(), "[1, 3) [19, 21)");// 新增添加区间覆盖所有分区的情况rl.add(1, 21);System.out.println(rl.toString()); // Should be: "[1, 21)"Assert.assertEquals(rl.toString(), "[1, 21)");// 新增移除区间覆盖所有分区的情况rl.remove(1, 21);System.out.println(rl.toString()); // Should be: ""Assert.assertEquals(rl.toString(), "");}void add(int start, int end) {add(new int[]{start, end});}/*** 新增一个区间到区间列表中** @param range - 整数数组*/void add(int[] range) {// 参数检查if (!checkParams(range)) {return;}// 原来的区间为空if (intervals.isEmpty()) {intervals.add(range);}// 存储新增&合并后的结果ArrayList<int[]> res = new ArrayList<>();// 记录res是否已经add输入的区间boolean hadInsert = false;for (int[] item : intervals) {// 1 不相交，后续元素存在相交可能性// 新增区间 = [10,12)// 遍历节点item = [6,8)if (item[1] < range[0]) {res.add(item);continue;}// 2 不相交，当前遍历节点start比输入的end大，在当前节点item前插入新节点，然后中止插入流程// 新增区间 = [1,3)// 遍历节点item = [6,8)if (item[0] > range[1]) {if (!hadInsert) {res.add(range);hadInsert = true;}res.add(item);continue;}// 3 以下是相交的情况// 3.1 新增区间完全包含覆盖遍历的节点item区间，丢弃或移除遍历节点// 新增区间 = [5,10)// 遍历节点item = [6,8)if (item[0] > range[0] && item[1] < range[1]) {continue;}// 3.2 新增区间前半部分与遍历的节点item相交，扩展新增区间start的范围至item[0]// 新增区间(原来) = [5,10)// 遍历节点item = [4, 6)// 新增区间(更新后) = [4,10)if (item[0] < range[0]) {range[0] = item[0];}// 3.3 新增区间后半部分与遍历的节点item相交，扩充新增区间end的范围至item[1]// 新增区间(原来) = [5,10)// 遍历节点item = [8, 12)// 新增区间(更新后) = [5,12)if (item[1] > range[1]) {range[1] = item[1];}}// 4 边界处理，可能需要把新增区间插入到结果列表中int[] last = res.size() == 0 ? range : res.get(res.size() - 1);if (res.size() == 0 || last[1] < range[0]) {res.add(range);}intervals = res;}void remove(int start, int end) {remove(new int[]{start, end});}/*** 从区间列表中移除一个区间** @param range 移除区间*/void remove(int[] range) {// 参数检查if (!checkParams(range)) {return;}// 原来的区间为空if (intervals.isEmpty()) {return;}// 存储新增&合并后的结果ArrayList<int[]> res = new ArrayList<>();for (int[] item : intervals) {// 1 不相交，直接加入到结果集中// 移除区间range = [10,12)// 遍历节点item = [6,8) 或 [14,15)if (range[1] <= item[0] || range[0] >= item[1]) {res.add(item);continue;}// 2 以下是相交的情况// 2.1 完全移除：移除区间range完全包含或覆盖遍历的节点item区间// 移除区间range = [5,10)// 遍历节点item = [6,8)if (range[0] <= item[0] && range[1] >= item[1]) {continue;}// 移除部分区间if (range[0] <= item[1]) {if (range[1] >= item[1]) {// 2.2 移除后部分：移除区间range前部与遍历的节点item后部相交，缩短遍历节点item的end范围至range[0]// 移除区间range =      [5,10)// 遍历节点item =       [4,6)// 遍历节点item(更新后) = [4,5)item[1] = range[0];res.add(item);} else {// 2.3 移除中间部分：原来区间拆分成[item[0], range[0])与[range[1], item[1]) 2部分// 移除区间range =      [5,10)// 遍历节点item =          [4,10)// 遍历节点item(更新后) =   [7,8)// 遍历节点拆分成2部分 =     [4,7) [8,10)if (range[0] > item[0]) {res.add(new int[]{item[0], range[0]});}res.add(new int[]{range[1], item[1]});}continue;}// 2.4 移除前部分：移除区间range后部分与遍历的节点item前部相交，缩短遍历节点start范围至range[1]// 移除区间range =      [5,10)// 遍历节点item =       [8,12)// 遍历节点item(更新后)= [10,12)if (range[1] > item[0]) {item[0] = range[1];res.add(item);}}intervals = res;}/*** 把区间列表转换成字符串** @return string*/@Overridepublic String toString() {StringBuilder builder = new StringBuilder();if (intervals.isEmpty()) {return builder.toString();}for (int i = 0; i < intervals.size(); i++) {int[] item = intervals.get(i);// 非第1个元素前面需要加1个空格if (i >= 1) {builder.append(BLANK);}builder.append(LEFT).append(item[0]).append(FLAG).append(item[1]).append(RIGHT);}return builder.toString();}/*** 参数校验** @param range 数组区间* @return boolean true=校验通过，false=校验不通过*/private boolean checkParams(int[] range) {// 参数及长度核验if (range == null || range.length < 2) {return false;}// 参数值核验return range[0] <= range[1];}
}