Problem
I’ve been given the following task:
Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. Input is represented by N lines with 4 numbers separated by spaces, defining 2 opposite vertices of the rectangle. Output file should contain 1 number – the resulting area of the rectangles’ union.
Additional constraints:
 1≤N≤100$1\le N\le 100$
 −10000≤x1$10000\le x1$, y1$y1$, x2$x2$, y2≤10000$y2\le 10000$
 Memory consumption < 16 MB
 Program parameters should be validated
 Input file format should be validated.
Examples:
Input:
1 1 7 7
Output:
36
Input:
1 1 3 3
2 2 4 4
Output:
7
My solution:
public class Main {
private List<Rectangle> rectangles = new ArrayList<>();
public static void main(String[] args) {
if (args.length != 2) {
throw new IllegalArgumentException("Invalid arguments numbernProgram usage: java Main input output");
}
Main computer = new Main();
long area = computer.computeAreaFromFile(args[0]);
computer.writeAreaToFile(area, args[1]);
}
public long computeAreaFromFile(String inputFileName) {
rectangles.clear();
String line;
try (BufferedReader inputFileReader = new BufferedReader(new FileReader(inputFileName))) {
long area = 0;
while ((line = inputFileReader.readLine()) != null) {
Rectangle rectangle = Rectangle.fromString(line);
area += addRectangleArea(rectangle, false);
}
return area;
} catch (FileNotFoundException e) {
throw new IllegalArgumentException("Input file not found");
} catch (IOException e) {
throw new RuntimeException(e);
} catch (NumberFormatException  IndexOutOfBoundsException e) {
throw new IllegalArgumentException("Input file contains incorrect line");
}
}
private int addRectangleArea(Rectangle newRectangle, boolean isIntersection) {
int result = 0;
boolean hasIntersections = false;
for (Rectangle existingRectangle : rectangles) {
if (!existingRectangle.contains(newRectangle)) {
List<Rectangle> complements = existingRectangle.complementOf(newRectangle);
if (complements.size() > 0) {
hasIntersections = true;
for (Rectangle complement : complements) {
result += addRectangleArea(complement, true);
}
break;
}
}
}
if (!hasIntersections) {
result += newRectangle.area();
}
if (!isIntersection) {
rectangles.add(newRectangle);
}
return result;
}
private void writeAreaToFile(long area, String outputFileName) {
try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
writer.write(String.valueOf(area));
} catch (IOException e) {
throw new RuntimeException("Could not open file " + outputFileName);
}
}
}
class Rectangle {
public final int x1;
public final int y1;
public final int x2;
public final int y2;
public static Rectangle fromString(String input) throws NumberFormatException, IndexOutOfBoundsException {
String[] splitInput = input.split(" ");
if (splitInput.length != 4) {
throw new IndexOutOfBoundsException();
}
return new Rectangle(Integer.valueOf(splitInput[0]),
Integer.valueOf(splitInput[1]),
Integer.valueOf(splitInput[2]),
Integer.valueOf(splitInput[3]));
}
public Rectangle(int x1, int y1, int x2, int y2) {
this.x1 = Math.min(x1, x2);
this.y1 = Math.min(y1, y2);
this.x2 = Math.max(x1, x2);
this.y2 = Math.max(y1, y2);
}
/**
* Finds a relative complement of the specified rectangle.
*
* @param rectangle rectangle to find a complement of.
* @return {@link List} of the rectangles forming the resulting complement.
*/
public List<Rectangle> complementOf(Rectangle rectangle) {
List<Rectangle> intersections = new ArrayList<>();
if (rectangle.x2 > x1 && x2 > rectangle.x1 && rectangle.y2 > y1 && y2 > rectangle.y1) {
if (rectangle.y1 <= y1) {
intersections.add(new Rectangle(rectangle.x1, rectangle.y1, rectangle.x2, y1));
}
if (y2 <= rectangle.y2) {
intersections.add(new Rectangle(rectangle.x1, y2, rectangle.x2, rectangle.y2));
}
if (rectangle.x1 <= x1) {
intersections.add(new Rectangle(rectangle.x1, Math.max(y1, rectangle.y1), x1, Math.min(y2, rectangle.y2)));
}
if (x2 <= rectangle.x2) {
intersections.add(new Rectangle(x2, Math.max(y1, rectangle.y1), rectangle.x2, Math.min(y2, rectangle.y2)));
}
}
return intersections;
}
/**
* Calculates area of this rectangle.
*
* @return area of this rectangle.
*/
public int area() {
return Math.abs((x1  x2) * (y1  y2));
}
/**
* Checks if this rectangle contains the specified rectangle.
*
* @param rectangle rectangle to check for.
* @return true if rectangle inside this, false otherwise.
*/
public boolean contains(Rectangle rectangle) {
return x1 <= rectangle.x1 && rectangle.x2 <= x2 && y1 <= rectangle.y1 && rectangle.y2 <= y2;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Rectangle)) {
return false;
}
Rectangle other = (Rectangle) o;
return x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2;
}
@Override
public int hashCode() {
int result = 17;
result = 37 * result + x1;
result = 37 * result + y1;
result = 37 * result + x2;
result = 37 * result + y2;
return result;
}
@Override
public String toString() {
return String.format("Rectangle with x1: %s y1: %s x2: %s y2: %s", x1, y1, x2, y2);
}
}
I have several questions/considerations:
 Is the provided solution correct?
 I assume the complexity of this algorithm is O(n2)$O({n}^{2})$. Can it be improved?
 I’ve overridden
toString()
,equals()
andhashCode()
methods, although I’ve never called them (excepttoString()
while debugging). Is it bad practise to do so?  I feel that comments in javadoc are lame. How can they be improved and are they necessary at all?
computeAreaFromFile()
does 2 things: it reads file content and performs actual calculations. I think this method should be split, however I’m not sure how I could do this.
Solution
The time for the approach you gave is in O(n2)$O({n}^{2})$.
Dec. 10, 2018
Details about a possible solution
This is Klee’s measure problem for d=2$d=2$.
Apparently, an optimal algorithm for this case exists and is called Bentley’s algorithm. Its running time is O(n⋅log(n))$O(n\cdot \mathrm{log}(n))$. However, it seems that the 1977 paper that describes it is unavailable. It uses sweepline approach and a dynamic 1d segment tree.
We have n$n$ axisaligned rectangles. Our sweepline moves across x$x$. We have events along x$x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweepline with a collection of rectangles is essentially a 1d measure problem. We have 2⋅n$2\cdot n$ events with at most 2⋅n$2\cdot n$ distinct x values. We use a 1d segment tree that we maintain via inserts and deletes to give 1d measure that we “pull” with deltax$x$‘s to give incremental contributions to 2d measure. The costly operations are sort and insert/delete.
Higher dimensions are more difficult to handle. We might then be better served by using higherdimensional segment tree with intersection queries or an Rtree variant with intersection queries. This would depend on which is larger — d ⋅log(n)$d\text{}\cdot \mathrm{log}(n)$ or logmax(d−1,1)(n)${\mathrm{log}}^{\text{max}(d1,1)}(n)$ for d≥1$d\ge 1$ — the former being smaller may imply that Rtree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.
For more details, see the links.
References

Bentley – Algorithms for Klee’s rectangle problems (1977) — possibly unavailable

Elizarov – Finding missing range in multidimensional domain – Answer (2017)
https://cs.stackexchange.com/q/73819 
Erickson – Klee’s measure problem (1998)
http://jeffe.cs.illinois.edu/open/klee.html 
Chlebus – On the Klee’s measure problem in small dimensions (1998)
Correctness
(See the update at the end.)
I don’t believe your algorithm is correct. Here is the way I would expect to see it solved:

Define a function
rectDiff(r,s)
which computes the difference of two rectanglesr
ands
. It may return an empty list (ifr
is completely contained ins
), a list of justr
(ifr
is disjoint froms
) or a list of two smaller rectanglesr1
,r2
representing the parts ofr
which do not intersects
. This is probably what your.complementsOf()
method does. 
Given this
rectDiff
function, I would compute the area like this:Pseudocode:
theRects = ...read rects from a file... rectangles = [] totalArea = 0 for r in theRects: pieces = [r] for s in rectangles: pieces = takeAway(pieces, s) for t in pieces: totalArea += area(t) append r to rectangles def takeAway(pieces, s): # pieces is a list of (disjoint) rects # s is a single rect # returns a new list of (disjoint) rects newPieces = [] for t in pieces: append rectDiff(t,s) to newPieces return newPieces
The point is that when considering a new rectangle
r
you need to remove fromr
the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.
Your code, however, adds the area of a complement right away to the total area.
Range trees
If you employ the ideas in this article, you can use range trees to write the code this way:
for r in theRectangles:
let rlist = the list of rects in rectangles which overlap with r
pieces = [r]
for s in rlist:
pieces = takeAway(pieces, s)
...
add r to rectangles
The idea is that using a range tree rlist
might be a lot smaller than the full list rectangles
.
Update
Your algorithm is probably correct since you recursively call addRectangleArea()
on each complement piece.
However, there is an inefficiency in the algorithm. Suppose:
rectangles = [ r1, r2, r3, ... ]
and we are processing a new rectangle r
. Let
cs1 = rectDiff(r, r1) = complements of r compared to r1
= [ c1, c2, ... ]
Your code calls addRectangleArea(c1)
which then will compute rectDiff(c1, r1)
. However, this difference will always be empty. When considering c1
(or c2
or any rectangle in cs1
) you can start with r2
in the rectangles
list on the recursive call.