##Reading Points
you have the method and class:
private static List<Point> readPoints(String line) {
List<Point> points = new ArrayList<>();
Scanner scanner = new Scanner(line);
while (scanner.hasNext()) {
int left = scanner.next();
int height = scanner.next();
int right = scanner.next();
points.add(new Point(left, height, true));
points.add(new Point(right, height, false));
}
}
This is to process data of the form:
(1,2,6);(9,23,22);(22,6,24);(8,14,19);(23,12,30)
The common way in Java to process input like this is to use a Matcher:
private static final Pattern POINT_PATTERN = Pattern.compile("\\((\\d+),(\\d+),(\\d+)\\);?");
private static List<Point> readPoints(String line) {
List<Point> points = new ArrayList<>();
Matcher matcher = POINT_PATTERN.matcher(line);
while (matcher.find()) {
int left = Integer.parseInt(matcher.group(1));
int height = Integer.parseInt(matcher.group(2));
int right = Integer.parseInt(matcher.group(3));
points.add(new Point(left, height, true));
points.add(new Point(right, height, false));
}
return points;
}
Note that the matcher looks for three comma-separated number-groups inside explicit parenthesis, with an optional trailing semi-colon. The parenthesis around the \\d+
in the pattern makes those available as groups. The (expanded) pattern is:
\( (\d+) , (\d+) , (\d+) \) ;?
^^^^^ ^^^^^ ^^^^^ ^^
| Group 1
| Group 2
| Group 3
| Optional ;
That would significantly simplify the code.
##Point
Your Point class implements Comparable. This is nice, but whenever you have a natural order implied with a class, you should also override equals()
and hashCode()
(the contract is that any two objects which have compareTo()
return 0, should also be equals()
.
The 'y' variable is also a bit of a poor name, I would prefer the name 'height'. While we are naming things, I would call the 'Point' class 'Event' too.
I used some bit-shifting to pre-calculate the hashCode.
I ended up with:
private static class Event implements Comparable<Event> {
private final boolean isStart;
private final int x;
private final int height;
private final int hash;
public Event(int x, int height, boolean isStart) {
this.x = x;
this.height = height;
this.isStart = isStart;
this.hash = ((isStart ? 1 : -1) * x) ^ (height << 16 | height >>> 16);
}
@Override
public int hashCode() {
return hash;
}
@Override
public boolean equals(Object obj) {
return obj == this || ((obj instanceof Event) && hashCode() == obj.hashCode() && compareTo((Event)obj) == 0);
}
@Override
public int compareTo(Event other) {
int result = Integer.compare(this.x, other.x);
if (result != 0) {
return result;
}
if (this.isStart == other.isStart) {
return this.isStart ? Integer.compare(other.height, this.height) : Integer.compare(this.height, other.height);
}
return this.isStart ? -1 : 1;
}
}
##Algorithm
It took me a while to understand the algorithm.
In general, i dislike the use of a Map<Integer,Integer>
because it is ugly that you have to check for the null value before you can increment the count (the value is a Counter of sorts).
This part is something I believe should have been rewritten as a separate class. A HeightTracker
class perhaps. The class could have a mutable inner class called Counter
that can be incremented/decremented in place. When it decrements to 0, it auto-removes from the Map. The removal of the autoboxing may lead to performance improvements, but those will be small.
The other observation I have is that the SortedMap should probably have a custom comparator that sorts in reverse-height order. This is another small item, but it is more intuitive to me to have a call to heights.firstKey()
rather than heights.lastKey()
The HeightTracker may even be better off as a completely custom class without the SortedMap at all. I would have to rewrite it myself to see.
Apart from these issues, the algorithm stikes me as being sound. It's not quite the same as some papers I read on the subject, but the performance time-complexity of \$O(n \log{n})\$ is in line with expectations.