References to similar questions:
56. Merge Intervals – LeetCode merge interval
57. Insert interval – LeetCode
1272. Delete interval
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 {
// result
private List<int[]> intervals = new ArrayList<>();
// Static constant used by toString
private static final String LEFT = "[";
private static final String RIGHT = ")";
private static final String FLAG = ", ";
private static final String BLANK = " ";
/**
* junit unit testing
*/
@Test
public 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)");
//Add the case where the removal interval does not exist
rl.remove(4, 18);
System.out.println(rl.toString()); // Should be: "[1, 3) [19, 21)"
Assert.assertEquals(rl.toString(), "[1, 3) [19, 21)");
// Added new situation of adding interval to cover all partitions
rl.add(1, 21);
System.out.println(rl.toString()); // Should be: "[1, 21)"
Assert.assertEquals(rl.toString(), "[1, 21)");
//Add the case where the removed range covers all partitions
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});
}
/**
* Add an interval to the interval list
*
* @param range - integer array
*/
void add(int[] range) {
//Parameter check
if (!checkParams(range)) {
return;
}
//The original range is empty
if (intervals.isEmpty()) {
intervals.add(range);
}
// Store the new & merged results
ArrayList<int[]> res = new ArrayList<>();
//Record whether res has added the input range
boolean hadInsert = false;
for (int[] item : intervals) {
// 1 is disjoint, subsequent elements may intersect
//New interval = [10,12)
// Traverse node item = [6,8)
if (item[1] < range[0]) {
res.add(item);
continue;
}
// 2 disjoint, the current traversal node start is larger than the input end, insert a new node before the current node item, and then stop the insertion process
//New interval = [1,3)
// Traverse node item = [6,8)
if (item[0] > range[1]) {
if (!hadInsert) {
res.add(range);
hadInsert = true;
}
res. add(item);
continue;
}
// 3 The following is the intersection situation
// 3.1 The newly added interval completely contains the node item interval covered by the traversal, discarding or removing the traversal node
// New interval = [5,10)
// Traverse node item = [6,8)
if (item[0] > range[0] & amp; & amp; item[1] < range[1]) {
continue;
}
// 3.2 The first half of the newly added interval intersects with the traversed node item, and the range of the newly added interval start is extended to item[0]
//New interval (original) = [5,10)
// Traverse node item = [4, 6)
// New interval (after update) = [4,10)
if (item[0] < range[0]) {
range[0] = item[0];
}
// 3.3 The second half of the newly added interval intersects with the traversed node item, expanding the range of the newly added interval end to item[1]
//New interval (original) = [5,10)
// Traverse node item = [8, 12)
//New interval (after update) = [5,12)
if (item[1] > range[1]) {
range[1] = item[1];
}
}
// 4 Boundary processing, it may be necessary to insert the new interval into the result list
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});
}
/**
* Remove an interval from the interval list
*
* @param range remove range
*/
void remove(int[] range) {
// parameter check
if (!checkParams(range)) {
return;
}
// The original range is empty
if (intervals.isEmpty()) {
return;
}
// Store the new & merged results
ArrayList<int[]> res = new ArrayList<>();
for (int[] item : intervals) {
// 1 does not intersect, directly added to the result set
//Remove interval range = [10,12)
// Traverse node item = [6,8) or [14,15)
if (range[1] <= item[0] || range[0] >= item[1]) {
res. add(item);
continue;
}
// 2 The following is the intersection situation
// 2.1 Completely remove: remove the interval range completely contains or cover the traversed node item interval
//Remove interval range = [5,10)
// Traverse node item = [6,8)
if (range[0] <= item[0] & amp; & amp; range[1] >= item[1]) {
continue;
}
// remove part of range
if (range[0] <= item[1]) {
if (range[1] >= item[1]) {
// 2.2 Remove the rear part: remove the intersection of the front part of the interval range and the rear part of the traversed node item, and shorten the end range of the traversed node item to range[0]
//Remove interval range = [5,10)
// Traverse node item = [4,6)
// Traverse node item (after update) = [4,5)
item[1] = range[0];
res. add(item);
} else {
// 2.3 Remove the middle part: the original range is split into two parts [item[0], range[0]) and [range[1], item[1])
//Remove interval range = [5,10)
// Traverse node item = [4,10)
// Traverse node item (after update) = [7,8)
// Traverse nodes split into 2 parts = [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 Remove the front part: the part after removing the interval range intersects with the front part of the traversed node item, shortening the traversed node start range to range[1]
//Remove interval range = [5,10)
// Traverse node item = [8,12)
// Traverse node item (after update) = [10,12)
if (range[1] > item[0]) {
item[0] = range[1];
res.add(item);
}
}
intervals = res;
}
/**
* Convert range list to string
*
* @return string
*/
@Override
public 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);
// A space needs to be added before the non-first element
if (i >= 1) {
builder.append(BLANK);
}
builder.append(LEFT).append(item[0]).append(FLAG).append(item[1]).append(RIGHT);
}
return builder.toString();
}
/**
* Parameter verification
*
* @param range array range
* @return boolean true=validation passed, false=validation failed
*/
private boolean checkParams(int[] range) {
// Parameter and length verification
if (range == null || range.length < 2) {
return false;
}
// Parameter value verification
return range[0] <= range[1];
}
}