Exclude matching intervals

Question

I have two lists of intervals. I would like to remove all the time from list1 that already exists in list2. Example: List1:

[(0.10), (15.20)]

List2:

[(2,3), (5,6)]

Output:

[(0.2), (3.5), (6.10), (15.20)]

Any clues?

Tried to delete one interval at a time, but it seems to me that I need to use a different approach:

public List<Interval> removeOneTime(Interval interval, Interval remove){ List<Interval> removed = new LinkedList<Interval>(); Interval overlap = interval.getOverlap(remove); if(overlap.getLength() > 0){ List<Interval> rms = interval.remove(overlap); removed.addAll(rms); } return removed; } 

Answer 1

I would approach this problem with a sweep algorithm. The start and end points of the intervals are events that are placed in the priority queue. You simply move from left to right, stop at each event, and update the current state in accordance with this event.

I made a small implementation in which I use the following Interval class, just for simplicity:

 public class Interval { public int start, end; public Interval(int start, int end) { this.start = start; this.end = end; } public String toString() { return "(" + start + "," + end + ")"; } } 

The event points mentioned earlier are represented by the following class:

 public class AnnotatedPoint implements Comparable<AnnotatedPoint> { public int value; public PointType type; public AnnotatedPoint(int value, PointType type) { this.value = value; this.type = type; } @Override public int compareTo(AnnotatedPoint other) { if (other.value == this.value) { return this.type.ordinal() < other.type.ordinal() ? -1 : 1; } else { return this.value < other.value ? -1 : 1; } } // the order is important here: if multiple events happen at the same point, // this is the order in which you want to deal with them public enum PointType { End, GapEnd, GapStart, Start } } 

Now what remains is to create a queue and perform a sweep, as shown in the code below

 public class Test { public static void main(String[] args) { List<Interval> interval = Arrays.asList(new Interval(0, 10), new Interval(15, 20)); List<Interval> remove = Arrays.asList(new Interval(2, 3), new Interval(5, 6)); List<AnnotatedPoint> queue = initQueue(interval, remove); List<Interval> result = doSweep(queue); // print result for (Interval i : result) { System.out.println(i); } } private static List<AnnotatedPoint> initQueue(List<Interval> interval, List<Interval> remove) { // annotate all points and put them in a list List<AnnotatedPoint> queue = new ArrayList<>(); for (Interval i : interval) { queue.add(new AnnotatedPoint(i.start, PointType.Start)); queue.add(new AnnotatedPoint(i.end, PointType.End)); } for (Interval i : remove) { queue.add(new AnnotatedPoint(i.start, PointType.GapStart)); queue.add(new AnnotatedPoint(i.end, PointType.GapEnd)); } // sort the queue Collections.sort(queue); return queue; } private static List<Interval> doSweep(List<AnnotatedPoint> queue) { List<Interval> result = new ArrayList<>(); // iterate over the queue boolean isInterval = false; // isInterval: #Start seen > #End seen boolean isGap = false; // isGap: #GapStart seen > #GapEnd seen int intervalStart = 0; for (AnnotatedPoint point : queue) { switch (point.type) { case Start: if (!isGap) { intervalStart = point.value; } isInterval = true; break; case End: if (!isGap) { result.add(new Interval(intervalStart, point.value)); } isInterval = false; break; case GapStart: if (isInterval) { result.add(new Interval(intervalStart, point.value)); } isGap = true; break; case GapEnd: if (isInterval) { intervalStart = point.value; } isGap = false; break; } } return result; } } 

This leads to:

 (0,2) (3,5) (6,10) (15,20) 

Answer 2

You probably want to use the interval tree, this will quickly tell you if the interval overlaps with any of the intervals in the tree.

Once you have a set of overlapping intervals, the task should be quite simple (interval1 from list1, interval2 is an overlapping interval from list2 / interval tree): if interval1 contains interval2, then you have two new intervals (interval1min, interval2min), (interval2max , interval 1max); if interval1 does not contain interval2, then you have only one new interval (interval1min, interval2min) or (interval2max, interval1max)