Algorithm suggestion
You can use a broom: have a data structure that represents what's going on in a single row that can be updated. Whenever you move to a new row, update it to take into account rectangles that appear or disappear in that row (which you can find by having a list of rectangle starts and ends and sorting that instead of just the list of rectangles).
The candidate for such a structure is a sorted dictionary that maps left ends of intervals to their IDs and right ends. You can simply amend it (by adding/removing the appropriate entry) and you can construct the spans by iterating over it while keeping aside a stack of still-open rectangles.
Algorithm suggestion
@loke
If you need to accept a stream of rectangles as input (i.e. can't keep all of them in memory), then you can keep a priority queue for the "rectangle end" events, where you'd insert an event when you encounter a beginning of a rectangle.