The interval covering problem
PointsCoveringIntervals.javaclass LeftComp implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
if (a.left < b.left) {
return -1;
}
if (a.left > b.left) {
return 1;
}
if (a.right < b.right) {
return -1;
}
if (a.right > b.right) {
return 1;
}
return 0;
}
}
class RightComp implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
if (a.right < b.right) {
return -1;
}
if (a.right > b.right) {
return 1;
}
if (a.left < b.left) {
return -1;
}
if (a.left > b.left) {
return 1;
}
return 0;
}
}
public static List<Integer> findMinimumVisits(
List<Interval> intervals) {
SortedSet<Interval> left = new TreeSet<>(new LeftComp());
SortedSet<Interval> right = new TreeSet<>(new RightComp());
for (Interval interval : intervals) {
left.add(interval);
right.add(interval);
}
List<Integer> s = new ArrayList<>();
while (!left.isEmpty() && !right.isEmpty()) {
int b = right.first().right;
s.add(b);
// Removes the intervals which intersect with R.cbegin().
Iterator<Interval> it = left.iterator();
while (it.hasNext()) {
Interval interval = it.next();
if (interval.left > b) {
break;
}
right.remove(interval);
it.remove();
}
}
return s;
}
PointsCoveringIntervalsAlternative.java
public static List<Integer> findMinimumVisits(List<Interval> I) {
List<EndPoint> endpoints = new ArrayList<>();
for (Interval aI : I) {
endpoints.add(new EndPoint(aI, true));
endpoints.add(new EndPoint(aI, false));
}
Collections.sort(endpoints);
return findMinimumVisitsHelper(endpoints);
}
private static List<Integer> findMinimumVisitsHelper(
List<EndPoint> endpoints) {
List<Integer> S = new ArrayList<>(); // A minimum set of visit times.
Set<Interval> covered = new HashSet<>();
List<Interval> covering = new ArrayList<>();
for (EndPoint e : endpoints) {
if (e.isLeft) {
covering.add(e.ptr);
} else if (!covered.contains(e.ptr)) {
// e's interval has not been covered.
S.add(e.ptr.right);
// Adds all intervals in covering to covered.
covered.addAll(covering);
covering.clear(); // e is contained in all intervals in covering.
}
}
return S;
}
