This is a solution to CodeEval's SkyScrapers challenge.
You are given a list of triples \$(l, h, r)\$. Each triple represents an axis-aligned rectangle, with top-left corner at \$(l, h)\$ and bottom-right corner at \$(r, 0)\$. You can imagine these rectangles as buildings against a skyline.
The task is to "draw" the skyline, by printing a list of points \$(x, h)\$ where the line drawing of the skyline changes from horizontal to vertical, and \$h\$ is the height of the vertical line.
For all heights \$h\$, \$1 \leq h \leq 100\$. For all \$x\$-coordinates, \$1 \leq x \leq 10{,}000\$. There are at most \$1{,}000\$ rectangles/buildings.
Examples:
Input: (1,2,3);(2,4,6);(4,5,5);(7,3,11);(9,2,14);(13,7,15);(14,3,17)
Output: 1 2 2 4 4 5 5 4 6 0 7 3 11 2 13 7 15 3 17 0
Input: (1,2,6);(9,23,22);(22,6,24);(8,14,19);(23,12,30)
Output: 1 2 6 0 8 14 9 23 22 6 23 12 30 0
The solution uses a sweep-line algorithm to find the points where the height of the outline changes.
Scanner is a silly class to parse the ridiculous input format. In an ideal world it wouldn't exist, but it shaved off a significant amount of time.
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
class Main {
public static void main(String[] args) {
try {
List<String> lines = Files.readAllLines(Paths.get(args[0]), StandardCharsets.UTF_8);
for (String line : lines) {
System.out.println(getSkyline(line));
}
} catch (IOException e) {
e.printStackTrace();
}
}
private static String getSkyline(String line) {
List<Point> points = readPoints(line);
Collections.sort(points);
StringBuilder sb = new StringBuilder();
SortedMap<Integer, Integer> heights = new TreeMap<>();
int height = 0;
for (Point point : points) {
int newHeight = getNewHeight(height, point, heights);;
if (newHeight != height) {
sb.append(point.x).append(' ').append(newHeight).append(' ');
height = newHeight;
}
}
return sb.deleteCharAt(sb.length() - 1).toString();
}
private static int getNewHeight(int height, Point point, SortedMap<Integer, Integer> heights) {
if (point.isStart) {
Integer count = heights.get(point.y);
heights.put(point.y, count == null ? 1 : count + 1);
return Math.max(height, point.y);
}
Integer count = heights.get(point.y) - 1;
if (count == 0) {
heights.remove(point.y);
if (point.y == height) {
return heights.isEmpty() ? 0 : heights.lastKey();
}
return height;
}
heights.put(point.y, count);
return height;
}
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));
}
return points;
}
private static class Point implements Comparable<Point> {
private final boolean isStart;
private final int x;
private final int y;
public Point(int x, int y, boolean isStart) {
this.x = x;
this.y = y;
this.isStart = isStart;
}
public int compareTo(Point other) {
int result = Integer.compare(this.x, other.x);
if (result == 0) {
if (this.isStart == other.isStart) {
return this.isStart ? Integer.compare(other.y, this.y) : Integer.compare(this.y, other.y);
}
return this.isStart ? -1 : 1;
}
return result;
}
}
private static class Scanner {
private final String line;
private final int length;
private int i;
public Scanner(final String line) {
this.line = line;
this.length = line.length();
}
public boolean hasNext() {
moveNext();
return this.i < this.length;
}
public int next() {
moveNext();
int n = 0;
int c;
while ((c = toInt(this.line.charAt(this.i))) != -1) {
n = n * 10 + c;
this.i++;
}
return n;
}
private void moveNext() {
while (this.i < this.length && toInt(this.line.charAt(this.i)) == -1) {
this.i++;
}
}
private static int toInt(char c) {
return (c >= '0' && c <= '9') ? c - '0' : -1;
}
}
}
