排除重叠间隔
我有两个间隔列表。 我想从列表2中已经存在的list1中删除所有时间。 示例：List1：
[（0,10），（15,20）]
列表2：
[（2,3），（5,6）]
输出：
[（0,2），（3,5），（6,10），（15,20）]
任何提示？
试图删除当时的一个间隔，但似乎我需要采取不同的方法：
public List removeOneTime(Interval interval, Interval remove){ List removed = new LinkedList(); Interval overlap = interval.getOverlap(remove); if(overlap.getLength() > 0){ List rms = interval.remove(overlap); removed.addAll(rms); } return removed; } 我会用扫描线算法来解决这个问题。 间隔的起点和终点是放在优先级队列中的事件。 您只需从左向右移动，在每个事件处停止，并根据该事件更新当前状态。
我做了一个小实现，其中我使用了以下Interval类，只是为了简单：
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 + ")"; } }
前面提到的事件点由以下类表示：
public class AnnotatedPoint implements Comparable { 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 } }
现在，剩下的就是构建队列并进行扫描，如下面的代码所示
public class Test { public static void main(String[] args) { List interval = Arrays.asList(new Interval(0, 10), new Interval(15, 20)); List remove = Arrays.asList(new Interval(2, 3), new Interval(5, 6)); List queue = initQueue(interval, remove); List result = doSweep(queue); // print result for (Interval i : result) { System.out.println(i); } } private static List initQueue(List interval, List remove) { // annotate all points and put them in a list List 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 doSweep(List queue) { List 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; } }
这导致：
(0,2) (3,5) (6,10) (15,20)
您可能希望使用间隔树 – 这将快速告诉您间隔是否与树中的任何间隔重叠。
一旦你有一组重叠的间隔，任务应该相当容易（interval1来自list1，interval2是list2 / interval树的重叠间隔）：如果interval1包含interval2，那么你有两个新的间隔（interval1min，interval2min）， （interval2max，interval1max）; 如果interval1不包含interval2，那么你只有一个新的间隔（interval1min，interval2min）或（interval2max，interval1max）