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