As these records were made before the age of computers & also really before even relatively simple modern vinyl cutting techniques were invented, they only really had two things they could play with...
Length.
Quite simply, it would be beneficial to them to be able to shorten each track as much as possible. Miss out a verse, shorten the number of choruses at the end, make the fade-out very rapid, etc.
Volume.
Because a vinyl record is a purely analog device, whereby each groove moves left/right for mono or left/right & up/down for stereo in relation to a pure circle [or spiral] when read at the stylus, the actual loudness at which the record is cut will affect how wide each groove will be & how close together they could set the grooves.
They could also apply a simple EQ curve - turn down the bass, as bass requires larger movement of the groove than treble does - to further reduce the width of track.
In modern computerised cutting, the computer can read ahead one or even two revolutions of the disk, & adjust the groove gap automatically, on the fly, if duration maximisation is required, or even to be able to get more volume in the cut.
In the days these records were cut, either someone would be guiding the track separation by hand, as the cut ran, or more likely it would just be set & left static for the entire duration of the cut; except for a slightly wider gap at the track borders.
Using some simple arithmetic -
t minutes equals n revolutions, which requires minimum track to track gap g.
At volume v, which produces a track width of w, can we fit n revolutions onto the side using track gap g.
If not, & assuming t is already as short as we can get it, then reduce volume v until we can.