Allocating People into Groups with Window aggregation

This is along the lines of more stupid window function fun and how many ways can we abuse this technology in PostgreSQL. Well actually we were using this approach to allocate geographic areas such that each area has approximately the same population of things. So you can imagine densely populated areas would have smaller regions and more of them and less dense areas will have larger regions but fewer of them (kind of like US Census tracts). So you have to think about ways of allocating your regions so you don't have a multipolygon where one part is in one part of the world and the other in another etc. Using window aggregation is one approach in conjunction with spatial sorting algorithms.

The non-spatial equivalent of this problem is how do you shove people in an elevator and ensure you don't exceed the capacity of the elevator for each ride. Below is a somewhat naive way of doing this. The idea being you keep on summing the weights until you reach capacity and then start a new grouping.

To test this idea out lets create a table of people and their weights. The capacity of our elevator is 750 kg.

CREATE TABLE passengers(passenger_name varchar(20) PRIMARY KEY, weight_kg integer);
INSERT INTO passengers(passenger_name, weight_kg)
VALUES ('Johnny', 60),
        ('Jimmy', 120),
        ('Jenny', 50),
        ('Namy', 20),
        ('Grendel', 500),
        ('Charlie', 200),
        ('Gongadin', 400),
        ('Tin Tin', 10),
        ('Thumb Twins', 10),
        ('Titan', 600),
        ('Titania', 550),
        ('Titan''s Groupie', 55);

SELECT carriage,COUNT(passenger_name) As cnt_pass, 
    array_agg(passenger_name) As passengers, SUM(weight_kg) As car_kg
FROM (SELECT passenger_name, weight_kg,
  ceiling(SUM(weight_kg) 
    OVER(ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)/750.00) As carriage
FROM passengers) As congregation
GROUP BY carriage
ORDER BY carriage;

The result looks like

 carriage | cnt_pass |                 passengers                 | car_kg
----------+----------+--------------------------------------------+--------
        1 |        5 | {Johnny,Jimmy,Jenny,Namy,Grendel}          |    750
        2 |        4 | {Charlie,Gongadin,"Tin Tin","Thumb Twins"} |    620
        3 |        1 | {Titan}                                    |    600
        4 |        2 | {Titania,"Titan's Groupie"}                |    605