This took me longer than I would have liked it to

area.py

#!usr/bin/env python


class Rectangle:
    """All rectangle methods are constant time."""

    def __init__(self, x1, y1, x2, y2):
        """Opposite corners of a rectangle.
        These points will not be changed once set."""
        assert(x1 != x2)
        assert(y1 != y2)

        self.x1 = x1
        self.x2 = x2
        self.y1 = y1
        self.y2 = y2

    def left(self):
        return min(self.x1, self.x2)

    def right(self):
        return max(self.x1, self.x2)

    def top(self):
        return max(self.y1, self.y2)

    def bottom(self):
        return min(self.y1, self.y2)

    def area(self):
        """Constant but can be optomized"""
        return abs(self.x1-self.x2) * abs(self.y1-self.y2)

    def contains(self, x, y):
        """
        Checks if the rectangle contains a point.

        Constant but can be optomized
        """
        return (min(self.x1, self.x2) < x < max(self.x1, self.x2) and
                min(self.y1, self.y2) < y < max(self.y1, self.y2))

    def intersects(self, other):
        """
        Returns:
            bool: True if the rectangles do intersect. False otherwise.

        Constant but can be optomized
        """
        return self.union(other) is not None

    def union(self, other):
        """
        Intersection between 2 rectangles.

        Returns:
            Optional(Rectangle): Returns intersecting rectangle if they do intersect.
                None otherwise.

        Constant but can be optomized
        """
        left = max(self.left(), other.left())
        right = min(self.right(), other.right())
        bottom = max(self.bottom(), other.bottom())
        top = min(self.top(), other.top())

        if left >= right or top <= bottom:
            return None
        return Rectangle(left, bottom, right, top)

    def __str__(self):
        return "Rectangle[x1={},y1={},x2={},y2={}]".format(
            self.x1, self.y1, self.x2, self.y2
        )

    def __hash__(self):
        """Constant but can be optomized"""
        return hash(tuple(self.x1, self.x2, self.y1, self.y2))

    def __eq__(self, other):
        """Constant but can be optomized"""
        return (self.x1 == other.x1 and
                self.x2 == other.x2 and
                self.y1 == other.y1 and
                self.y2 == other.y2)


def powerset(s):
    """
    Assumption: s is a set, so all items in it are unique

    Args:
        s(list[Any])

    Returns:
        list[list[Any]]

    O(n^n) time complexity, but ideally powerset is 2^n
    """
    if not s:
        return [[]]
    else:
        current = s[0]
        p_rest = powerset(s[1:])  # linear slice

        # Add current to powerset of rest
        inclusions = []
        for other_set in p_rest:
            inclusions.append([current] + other_set)
        return inclusions + p_rest


def organized_powerset(s):
    """
    Sort the powerset by descending size order and pack the sets of the same
    size.

    organized_powerset([1, 2, 3]) == [[[]],
                                      [[1], [2], [3]],
                                      [[1, 2], [2, 3], [1, 3]],
                                      [[1, 2, 3]]]

    O(n^n) time complexity; dominated by poweset function
    """
    ps = powerset(s)

    # Linear
    container = [[] for i in range(len(s) + 1)]
    for s in ps:
        container[len(s)].append(s)

    return container


def unionize(rectangles):
    """Take the intersection of a sequence of rectangles.
    If any one of them does not intersect any of the others, there is no
    intersection.

    Linear
    """
    if not rectangles:
        return None

    ref = rectangles[0]
    for other in rectangles[1:]:
        union = ref.union(other)
        if union:
            ref = union
        else:
            return None

    return ref


def total_area(rectangles):
    """Find the total area of a sequence of potentially overlapping
    rectangles.

    O(n^n) complexity; dominated by powerset
    """
    p_rectagles = organized_powerset(rectangles)

    area = 0

    # First contains empty set
    for i in range(1, len(p_rectagles)):  # n^3
        if i % 2:
            # Addative
            sign = 1
        else:
            # Subtract
            sign = -1

        group = p_rectagles[i]

        # Take union of each sub group
        unions = []
        for subgroup in group:  # n^2
            union = unionize(subgroup)  # linear
            if union:
                unions.append(union)

        area += sign * sum(u.area() for u in unions)

    return area


def test_powerset():
    s = [1, 2, 3]
    p_s = powerset(s)
    assert(len(p_s) == 2**len(s))

    expected = [
        [1, 2, 3],
        [1, 2], [2, 3], [1, 3],
        [1], [2], [3],
        [],
    ]

    for answer in expected:
        assert(answer in p_s), "{} not in {}".format(answer, p_s)

    p_s_sorted = organized_powerset(s)
    assert(all(map(lambda x: len(x) == 0, p_s_sorted[0])))
    assert(all(map(lambda x: len(x) == 1, p_s_sorted[1])))
    assert(all(map(lambda x: len(x) == 2, p_s_sorted[2])))
    assert(all(map(lambda x: len(x) == 3, p_s_sorted[3])))


def test_total_area():
    # Null test
    assert(total_area([]) == 0)

    # Just 1
    r = [Rectangle(-1, -1, 1, 1)]
    assert(total_area(r) == 4)

    # No overlap
    r = [Rectangle(-1, -1, 1, 1),  # 4
         Rectangle(1, 1, 2, 2),  # 1
         Rectangle(-2, 0, -3, 3)]  # 3
    assert(total_area(r) == 8)

    # Overlap between 2
    r = [Rectangle(-1, -1, 1, 1),  # 4
         Rectangle(0, 0, 2, 2),  # 4 (overlaps with first)
         Rectangle(-2, 0, -3, 3)]  # 3
    assert total_area(r) == 10

    # Overlap between 3
    r = [Rectangle(-1, -1, 1, 1),  # 4
         Rectangle(0, 0, 2, 2),  # 4
         Rectangle(0, 0, -3, -3)]  # 9
    assert(total_area(r) == 15)

    # Overlap 4
    r = [Rectangle(-1, -1, 1, 1),  # 4
         Rectangle(0, 0, 2, 2),  # 4
         Rectangle(0, 0, -3, -3),  # 9
         Rectangle(-1, 1, 1, -4)]  # 10 (overlaps all; consumes 1st)
    assert total_area(r) == 19

    # Overlap 4 with one dominant rectangle
    r = [Rectangle(-1, -1, 1, 1),  # 4
         Rectangle(0, 0, 2, 2),  # 4
         Rectangle(0, 0, -3, -3),  # 9
         Rectangle(-4, -4, 4, 4)]  # 64 (consumes all)
    assert(total_area(r) == 64)

    r = [Rectangle(-2, 1, 0, -1),  # 4
         Rectangle(-1, 0, 1, 2),  # 4
         Rectangle(2, 1, 0, -1),  # 4
         Rectangle(-1, 0, 1, -2)]  # 4
    assert(total_area(r) == 12)


def main():
    test_powerset()
    test_total_area()


if __name__ == "__main__":
    main()