Find Intervals with Most Overlaps

Question

Given a list of time intervals, I want to return the intervals with the most overlaps (i.e. most people free). My solution runs in \$O(n \log n)\$, but I made a bunch of "tracker" variables. How can I avoid creating all these variables?

Interval class:

public class Interval {
    int start;
    int finish;

    public Interval(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

Point class (used in my algorithm):

public class Point implements Comparable<Point> {
    int time;
    TimeType type;

    public Point(int time, TimeType type) {
        this.time = time;
        this.type = type;
    }

    public int compareTo(Point p) {
        if (time == p.time) {
            if (!type.equals(p.type)) {
                if (type == TimeType.Finish) {
                    return -1;
                }
                return 1;
            }
            return 0;
        }
        return time - p.time;
    }
}

TimeType enum:

public enum TimeType {
    Start, Finish
}

The method that returns overlapping intervals:

public List<Interval> getOverlappingIntervals(List<Interval> intervals) {
        List<Point> sortedTimes = new ArrayList<Point>();
        Map<Point, Interval> map = new HashMap<Point, Interval>();
        Map<Point, Point> pointMap = new HashMap<Point, Point>();
        List<Interval> res = new ArrayList<Interval>();
        List<Point> currPartial = new LinkedList<Point>();
        List<Point> bestPartial = new LinkedList<Point>();
        int overallBest = 0;
        int currBest = 0;

        for (Interval i : intervals) {
            Point startPoint = new Point(i.start, TimeType.Start);
            Point endPoint = new Point(i.finish, TimeType.Finish);
            sortedTimes.add(startPoint);
            sortedTimes.add(endPoint);
            map.put(startPoint, i);
            pointMap.put(endPoint, startPoint);
        }

        Collections.sort(sortedTimes);

        for (int i = 0; i < sortedTimes.size(); i++) {
            Point curr = sortedTimes.get(i);
            if (curr.type.equals(TimeType.Start)) {
                currBest++;
                currPartial.add(sortedTimes.get(i));
            } else {
                currBest--;
                if (currBest == 0) {
                    currPartial.clear();
                } else {
                    currPartial.remove(pointMap.get(sortedTimes.get(i)));
                }
            }
            if (currBest > overallBest) {
                overallBest = currBest;
                bestPartial = new LinkedList<Point>(currPartial);
            }
        }

        for (Point p : bestPartial) {
            res.add(map.get(p));
        }

        return res;
    }

Answer 1

Is it really \$O(n\log n)\$?

Inside your main loop, you have this line:

            currPartial.remove(pointMap.get(sortedTimes.get(i)));

which removes a Point object from a linked list. This takes \$O(n)\$ time, so your whole algorithm takes \$O(n^2)\$ time.

Not only that, but this line which copies the best list so far is also \$O(n)\$ time:

           bestPartial = new LinkedList<Point>(currPartial);

Possible fixes

You could fix the first problem by using a data structure other than a LinkedList. For example, you could use a HashSet or LinkedHashSet.

You could fix the second problem by not making a copy of the best solution. Instead, remember the index i of the best solution. Then when you want to print the best solution, make another pass through the sorted times doing exactly what the first pass did. This time, however, you stop at the best index and print the contents of currPartial at that index.

Answer 2

Beware overly common names

public class Point implements Comparable<Point> {

Consider changing this to something else, e.g.

public class IntervalBoundary implements Comparable<IntervalBoundary> {

Point is already heavily used as a name for points in space. For example, Java's Abstract Window Toolkit (AWT) has a Point class and is heavily used in Java graphical user interfaces (GUIs).

Also consider making this a nested class. Then it wouldn't conflict if you used Interval and some other type of Point in the same application.

All enum implement Comparable

            if (!type.equals(p.type)) {
                if (type == TimeType.Finish) {
                    return -1;
                }
                return 1;
            }
            return 0;

Java.lang.Enum implements Comparable (and Serializable but that doesn't matter now). So you can just say

            return type.compareTo(p.type);

Use your helper class

        List<Point> sortedTimes = new ArrayList<Point>();
        Map<Point, Interval> map = new HashMap<Point, Interval>();
        Map<Point, Point> pointMap = new HashMap<Point, Point>();

You create three parallel data structures working with your helper class. You could get this down to just

        List<Point> sortedTimes = new ArrayList<Point>();

if you change Point to know what its opposite point is and to what interval it belongs

    private class Boundary implements Comparable<Boundary> {
        int time;
        TimeType type;
        Interval interval;
        Boundary opposite;

        public Boundary(int time, TimeType type, Interval interval) {
            this.time = time;
            this.type = type;
            this.interval = interval;
        }

        public Boundary(int time, TimeType type, Interval interval, Boundary start) {
            this(time, type, interval);
            this.opposite = start;
        }

        public void setOpposite(Boundary opposite) {
            this.opposite = opposite;
        }

        public Boundary getOpposite() {
            return opposite;
        }

        public Interval getInterval() {
            return interval;
        }

        public int compareTo(Boundary p) {
            if (time == p.time) {
                if (type == p.type) {
                    if (opposite.time == p.opposite.time) {
                        return opposite.type.compareTo(p.opposite.type);
                    }

                    return Integer.compare(opposite.time, p.opposite.time);
                }

                return type.compareTo(p.type);
            }

            return Integer.compare(time, p.time);
        }
    }

Then you don't need the extra data structures.

I also changed the name to Boundary as causing fewer name conflicts. I decided that was sufficient since I nested it inside another class.

Collections know their size

            if (curr.type.equals(TimeType.Start)) {
                currBest++;
                currPartial.add(sortedTimes.get(i));
            } else {
                currBest--;
                if (currBest == 0) {
                    currPartial.clear();
                } else {
                    currPartial.remove(pointMap.get(sortedTimes.get(i)));
                }
            }
            if (currBest > overallBest) {
                overallBest = currBest;
                bestPartial = new LinkedList<Point>(currPartial);
            }

So currBest is 0 when currPartial is empty. It increases when you add to currPartial. It decreases when you remove from currPartial. In fact, it is just the size of currPartial. So just say that.

            if (curr.type.equals(TimeType.Start)) {
                currPartial.add(sortedTimes.get(i));
            } else {
                currPartial.remove(pointMap.get(sortedTimes.get(i)));
            }

            if (currPartial.size() > bestPartial.size()) {
                bestPartial = new LinkedList<Point>(currPartial);
            }

Now you don't have to maintain two of the extra variables.