Programming Challenges

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);
    }

}