Inspired by @user2566092's answer I came up with a different method.
First, here is an example with a 'hole':
[1.3]
[6..9]
[8...12]
This should result in:
[1.3]
[6,8]
[8,9]
[9..12]
To get this, first determine the set of unique endpoints and order it:
1, 3, 6, 8, 9, 12
Then iterate over all possible sub intervals A-B formed by consecutive pairs:
[1,3]
[3,6]
[6,8]
[8,9]
[9,12]
For each interval A-B try to find an original interval X-Y which intersects with A-B. This is the case if:
(B > X) && (Y > A)
For example:
[A=1, B=3] is included because of [X=1, Y=3]
[A=3, B=6] is excluded, interval [X=1, Y=3] is excluded because Y=A,
the other original intervals are excluded because B<X
EDIT: Here is a Java implementation.
import java.util.*;
public class Main {
public static void main(final String[] args) {
determineSubIntervals(new Interval[] { new Interval(1, 5), new Interval(4, 9), new Interval(6, 12), new Interval(11, 17) });
determineSubIntervals(new Interval[] { new Interval(1, 3), new Interval(6, 9), new Interval(8, 12) });
}
private static List<Interval> determineSubIntervals(final Interval[] originals) {
System.out.println("Originals: " + Arrays.toString(originals));
final Set<Integer> endpoints = extractOrderedUniqueEndpoints(originals);
final List<Interval> candidates = createConsecutiveIntervals(endpoints);
final List<Interval> subIntervals = removeDisjunct(candidates, originals);
System.out.println("Sub intervals: " + subIntervals);
return subIntervals;
}
private static Set<Integer> extractOrderedUniqueEndpoints(final Interval[] intervals) {
final Set<Integer> endpoints = new TreeSet<Integer>();
for (final Interval interval : intervals) {
endpoints.add(interval.getStart());
endpoints.add(interval.getEnd());
}
return endpoints;
}
private static List<Interval> createConsecutiveIntervals(final Set<Integer> endpoints) {
final List<Interval> intervals = new ArrayList<Interval>();
final Iterator<Integer> it = endpoints.iterator();
Integer start = null;
while (it.hasNext()) {
final Integer end = it.next();
if (start != null) {
final Interval candidate = new Interval(start, end);
intervals.add(candidate);
}
start = end;
}
return intervals;
}
private static List<Interval> removeDisjunct(final List<Interval> candidates, final Interval[] intervals) {
final Iterator<Interval> it = candidates.iterator();
while (it.hasNext()) {
final Interval candidate = it.next();
if (isDisjunct(candidate, intervals)) {
it.remove();
}
}
return candidates;
}
private static boolean isDisjunct(final Interval candidate, final Interval[] intervals) {
final int a = candidate.getStart();
final int b = candidate.getEnd();
for (final Interval interval : intervals) {
final int x = interval.getStart();
final int y = interval.getEnd();
if ((b > x) && (y > a)) {
return false;
}
}
return true;
}
}
The Interval class:
public class Interval {
private final int start;
private final int end;
public Interval(final int start, final int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
@Override
public String toString() {
return String.format("[%s,%s]", start, end);
}
}
Output:
Originals: [[1,5], [4,9], [6,12], [11,17]]
Sub intervals: [[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]]
Originals: [[1,3], [6,9], [8,12]]
Sub intervals: [[1,3], [6,8], [8,9], [9,12]]
[1,4]and[4,5]overlaps. The "non-overlapping" interval set representing your intput would be the singleton[1,17]. – Rerito