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

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

        return res;
    }
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&lt;Point&gt;(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.