Links from class:
- Today’s contest
- Solutions to today’s contest
- Today’s slides
- Discussion on coin change problem
- TopCoder tutorial on binary search and bisection
- Lexicographical ordering
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>();
intervals.add(new Interval(0, 2));
intervals.add(new Interval(0, 3));
intervals.add(new Interval(1, 3));
intervals.add(new Interval(2, 5));
intervals.add(new Interval(4, 6));
intervals.add(new Interval(4, 7));
intervals.add(new Interval(6, 9));
intervals.add(new Interval(7, 8));
intervals.add(new Interval(8, 11));
intervals.add(new Interval(9, 13));
intervals.add(new Interval(10, 13));
findSmallestCovering(intervals);
findLargestDisjointSet(intervals);
}
}
For next class
Assigned readings:
- Read sections 3.3 and 3.4
Assigned problems:
- None. Catch up on problems from previous classes.
- Choose a midterm problem from a selection I’ve sent to you.