[SOLVED] Distributing a set of rectangles vertically to prevent any overlaps in R

I have a set of rectangles (stored as a set of xmin,ymin and xmax,ymax coordinates in an R data frame), some of which overlap, that I would like to plot on a chart and distribute them along the y-axis so that no two rectangles overlap. Their x coordinates must stay preserved; I need to achieve the goal by shifting the rectangles only vertically.

A concrete example:

df <- structure(list(xmin = c(67.705914, 6.005184, 66.162244, 87.99481, 
46.082243, 16.280928, 47, 3.4155154, 23.347187, 84.895525, 82.80274, 
16.85878, 4.3557265, 6.625263, 7.626907, 96.220383, 12.115471, 
30.235073, 46.082243, 16.280928, 79.90225, 29.42548, 84.895525, 
23.347184, 3.198581, 7.2832146, 25.539455, 1.695044, 34.425616, 
3.87074, 78.284034, 89.64427, 87.0506, 87.68941, 75.329986, 2.213225, 
3.4155154, 4.6098725, 0.5424367, 80.416396, 12.115471, 6.625263, 
32.722494, 8.344733, 89.64427, 52.48499, 90.12926, 30.235073, 
2.9885126, 8.719267), xmax = c(73.705914, 12.005184, 72.162244, 
93.99481, 52.082243, 22.280928, 53, 9.4155154, 29.347187, 90.895525, 
88.80274, 22.85878, 10.3557265, 12.625263, 13.626907, 102.220383, 
18.115471, 36.235073, 52.082243, 22.280928, 85.90225, 35.42548, 
90.895525, 29.347184, 9.198581, 13.2832146, 31.539455, 7.695044, 
40.425616, 9.87074, 84.284034, 95.64427, 93.0506, 93.68941, 81.329986, 
8.213225, 9.4155154, 10.6098725, 6.5424367, 86.416396, 18.115471, 
12.625263, 38.722494, 14.344733, 95.64427, 58.48499, 96.12926, 
36.235073, 8.9885126, 14.719267), ymin = c(15.6854458039728, 
29.280227138751, 85.6077652217337, 11.1447959143222, 88.6507847970509, 
47.8780668201714, 58.249961106352, 20.7963843697899, 39.1374442773956, 
14.253314246173, 31.2038928836167, 75.406238562994, 90.8407922528565, 
34.3969058783788, 90.0758115822633, 47.8810408921933, 41.9826622904241, 
18.4008825788269, 64.0816967514961, 26.1344753018713, 87.6969580943045, 
29.8031653049004, 25.5889076966207, 24.8832114234653, 65.6939979329678, 
83.7251558885676, 62.3262453418105, 52.1180170583712, 22.2274072090833, 
46.6403205808079, 51.4982774017124, 52.9611597344073, 86.5149513741532, 
8.71673006759099, 73.63580649852, 10.2390589604505, 79.6728413001311, 
27.0399934909858, 17.2084996917785, 28.7198728007395, 27.7845507714287, 
64.8898031132345, 77.518346688506, 11.785758214691, 51.2219947101639, 
55.4683310942946, 59.4959604756725, 15.6990628891733, 53.6174786549635, 
49.4079504426206), ymax = c(17.2907089618675, 31.2234089569328, 
87.3295043521685, 13.2730010425273, 90.8437672531913, 50.9203203412982, 
60.4271762962254, 23.1819265384646, 41.6096664996178, 15.6887703563279, 
34.0475653401924, 77.3496347894091, 93.4576597227361, 37.1520079191952, 
92.2237107419272, 52.1189591078067, 43.7265046549561, 21.6912051594721, 
65.7843994541988, 28.3922072606342, 89.9154454892625, 33.7570368040767, 
27.4828470905601, 26.6122436815298, 69.5273312663012, 86.1164074074011, 
64.1048569740807, 55.1107177882982, 23.6523109318047, 48.9688920093793, 
54.4445139608521, 55.219401492649, 88.3781992374011, 11.2337368703121, 
75.7899915205464, 13.1508236663329, 85.2391063603721, 29.4730210139216, 
20.1518959181936, 33.1198728007395, 30.7228223763669, 66.81402503475, 
79.1315542356758, 13.8413137702466, 52.7337440574224, 57.6201635550276, 
61.8678354756725, 19.1313772996537, 55.6110888786056, 51.560255051839
)), row.names = c(NA, -50L), class = "data.frame")

ggplot(df,aes(xmin=xmin,xmax=xmax,ymin=ymin,ymax=ymax)) + geom_rect(color="black",fill="cyan") + theme_void()

results in

whereas I would need something like this

Is there a way how to achieve this in R?

I have encountered a few similar posts thorough the web, most notably here, here, or here, but none of them seem to solve my problem of distributing rectangles only vertically to prevent overlaps, and in the R language.

What I have tried out of desperation is randomly shifting the rectangles using the swarmy function from the beeswarm package an checking for overlaps, but this is not usable as with a large number of rectangles, you could wait ages till the random algorithm finds a solution.

EDIT

Following the advice given in Dave's answer (any drawing some inspiration from Marcus's answer), I made a working piece of code:

library(ggplot2)

#' tests if a rectangle overlaps with any other rectangle from a set of rectangles
#'
#' @param testRect the rectangle to be tested for overlaps (in the form of any structure having the $xmin, $xmax, $ymin, and $ymax attributes)
#' @param rectList a data frame with the xmin, xmax, ymin, and ymax columns containing the set of rectangles to test the overlaps with
#' @returns a Boolean value, TRUE if there any any overlaps, FALSE if there are not
#' 
overlaps_any <- function(testRect, rectList) {
  if(nrow(rectList)==0) {
    return(FALSE)
  }
  for (r in 1:nrow(rectList)) {
    # If rectangle has area 0, no overlap
    if (testRect$xmin == testRect$xmax || testRect$ymax == testRect$ymin || rectList[r,"xmin"] == rectList[r,"xmax"] || rectList[r,"ymax"] == rectList[r,"ymin"]) {
      next
    }
    
    # If one rectangle is on the left side of the other
    if (testRect$xmin > rectList[r,"xmax"] || rectList[r,"xmin"] > testRect$xmax) {
      next
    }
    
    # If one rectangle is above the other
    if (testRect$ymin > rectList[r,"ymax"] || rectList[r,"ymin"] > testRect$ymax) {
      next
    }
    return(TRUE)
  }
  return(FALSE)
}

# Create an empty data frame
df.new <- data.frame()

# Iterate over each row of the original data frame
for(r in 1:nrow(df)) {
  # Select the rectangle from the original data frame
  testRect <- df[r,]
  
  # Calculate the height of the rectangle
  rect_height <- testRect$ymax - testRect$ymin
  
  # Set the minimum y-coordinate of the rectangle to 0
  testRect$ymin <- 0
  
  # Set the maximum y-coordinate of the rectangle based on the height
  testRect$ymax <- testRect$ymin + rect_height
  
  # Check if the rectangle overlaps with any existing rectangles in the new data frame
  while(overlaps_any(testRect, df.new)) {
    # Increment the y-coordinates of the rectangle by 1 to avoid overlap
    testRect$ymin <- testRect$ymin + 1
    testRect$ymax <- testRect$ymax + 1
  }
  
  # Append the updated rectangle to the new data frame
  df.new <- rbind(df.new, testRect)
}

# Plot the rectangles using ggplot
print(
  ggplot(df.new, aes(
    xmin = xmin,
    xmax = xmax,
    ymin = ymin,
    ymax = ymax
  )) +
    geom_rect(color = "black", fill = "cyan") + coord_fixed() + theme_void()
)

Result: