Wenn die Rechtecke alle ganzzahlige Positionen und Größen haben (Integer), dann kannst du einen einfachen "bildbasierten" Ansatz umsetzen. Zu Beginn markierst du alle "Pixel" innerhalb der roten Rechtecke als "abgedeckt". Jetzt iterierst du so lange es noch nicht abgedeckte "Pixel" gibt: Finde das erste "Pixel", das noch nicht abgedeckt ist, und lass dort ein neues grünes Rechteck starten. Lass es so weit wachsen wie möglich, solange es keine bereits abgedeckten "Pixel" überlappt. Du kannst z. B. abwechselnd in x- und y-Richtung vergrößern, bis keine Richtung mehr geht. Dann fügst du dieses Rechteck in die Ergebnisliste ein und markierst die darin liegenden "Pixel" als "abgedeckt".
Wenn die Rechtecke nicht ganzzahlig sind oder die Dimensionen zu groß sind, dann geht der Ansatz etwas abgewandelt trotzdem. Deine "Pixel" sind dann jedoch unregelmäßig. Dann unterteilst du dein "Koordinatengitter" an jeder x-Stelle bzw. y-Stelle, an der irgendein rotes Rechteck startet oder endet.