Rearrange house numbers into sorted, duplicate-free neighborhoods

A city is a list of neighborhoods. Each neighborhood is a list of house numbers (integers), and numbers may repeat, both within a neighborhood and across the city.

Move houses between neighborhoods so that:

1. Every neighborhood keeps its original size (the number of houses in it does not change).
2. No neighborhood holds the same house number twice.
3. Each neighborhood is listed in ascending order.

The city as a whole must keep exactly the same house numbers with the same counts. You only move houses; you never add, remove or renumber them.

Implement:

def rearrange_houses(houses: list[list[int]]) -> list[list[int]]:
    ...

Return any arrangement that meets all three rules, or [] if none exists. Empty neighborhoods are allowed and must stay empty.

Constraints

• 0 <= len(houses) <= 10^5
• Total number of houses N <= 2 * 10^5
• House numbers fit in a 32-bit signed integer.

Example 1

Input:  [[4, 4, 7], [2, 4], [7, 2, 9]]
Output: [[2, 4, 7], [4, 7], [2, 4, 9]]   (one valid answer)

Sizes stay 3, 2, 3. The three 4s, two 7s and two 2s each land in different neighborhoods.

Example 2

Input:  [[1, 1, 2], [2]]
Output: []

The first neighborhood needs three different numbers, but the city only has two distinct numbers (1 and 2).

Reconstructed from the reported question; details may differ from what interviewers ask.