# Programming Challenges

23 Jul 2013

## Intervals

In Java, the best way to represent intervals is by creating a simple class that contains the start and finish points. Using Comparators, you can simply sort them how you please using the standard Collections.sort() method.

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Intervals {

class Interval {
int a, b;

public Interval(int aa, int bb) {
a = aa;
b = bb;
}

public String toString() {
return String.format("(%d, %d)", a, b);
}
}

public static void main(String[] args) throws Exception {
new Intervals().run();
}

public void findSmallestCovering(ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval X, Interval Y) {
if (X.a < Y.a) { // Leftmost intervals should appear first
return -1;
} else if (X.a > Y.a) {
return 1;
} else if (X.b < Y.b) { // Longer intervals should appear before shorter ones
return 1;
} else if (X.b > Y.b) {
return -1;
} else { // The same interval
return 0;
}
}
});

System.out.printf("Sorted intervals: %s\n", intervals);

boolean covers = true;
int lastCoveredPoint = 0;
int greatestCoveredPoint = -1;
int greatestCoveredIndex = -1;
int intervalCount = 0;

for (int i = 0; i < intervals.size(); i++) {
Interval j = intervals.get(i);
if (j.a > lastCoveredPoint) {
if (greatestCoveredPoint == -1) {
covers = false;
break;
} else {
lastCoveredPoint = greatestCoveredPoint;
intervalCount++;
greatestCoveredPoint = -1;
System.out.println(intervals.get(greatestCoveredIndex));
}
}

if (j.a <= lastCoveredPoint && lastCoveredPoint <= j.b) {
int right = j.b;
if (right > greatestCoveredPoint) {
greatestCoveredPoint = Math.max(greatestCoveredPoint, j.b);
greatestCoveredIndex = i;
}
}
}

if (covers) {
System.out.printf("The smallest interval cover set contains %d intervals\n", intervalCount);
} else {
System.out.println("No cover!");
}
}

public void findLargestDisjointSet(ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval X, Interval Y) {
if (X.b < Y.b) { // Intervals that end earlier should appear first
return -1;
} else if (X.b > Y.b) {
return 1;
} else if (X.a < Y.a) { // Intervals that start later should appear first
return -1;
} else if (X.a > Y.a) {
return 1;
} else { // The same interval
return 0;
}
}
});

System.out.printf("Sorted intervals: %s\n", intervals);

int intervalCount = 0;
int lastCoveredPoint = -1;

for (int i = 0; i < intervals.size(); i++) {
Interval j = intervals.get(i);
if (j.a > lastCoveredPoint) {
System.out.println(j);
lastCoveredPoint = j.b;
intervalCount++;
}
}

System.out.printf("The number of intervals for the largest disjoint set is %d\n", intervalCount);
}

public void run() throws Exception {
ArrayList<Interval> intervals = new ArrayList<Interval>();

findSmallestCovering(intervals);

findLargestDisjointSet(intervals);
}

}
``````