Find Intervals with Most Overlaps

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 {
    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 getOverlappingIntervals(List intervals) {
List sortedTimes = new ArrayList();
Map map = new HashMap();
Map pointMap = new HashMap();
List res = new ArrayList();
List currPartial = new LinkedList();
List bestPartial = new LinkedList();
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 overallBest) {
overallBest = currBest;
bestPartial = new LinkedList(currPartial);
}
}

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(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.

StackExchange Code Review Q#138317, answer score: 5