One possible solution that comes to mind:
You said that each rectangle holds pointers to all the objects it will hit when moving right. I would suggest, take the list of pointers from the big rectangle (the one pointed by the arrow), take all it's nodes (the rectangles it would collide), find the min width, then do the same of all the child nodes, add the widths for each branch recursively. Treat the problem like a tree depth problem. Every node has a min width value so the answer to your question would be the distance between the wall and the x value of the right edge of the big rectangle minus the GREATEST sum of the least width of the rectangles. Create a vector where the depth (sum of min widths) of each branch of the tree is stored and find the max value. Distance minus max is your answer.
imagine the same picture with 4 boxes. one to the left, one to the right and then the wall. lets name them box 1, box 2 (mid top), box 3 (mid bottom) and the last one box 4 (right). each box has a width of 4. all can shrink except the left one. box 2 can shrink by 2, box 3 can shrink by 1, box 4 can shrink by 2. Calculating the 2 branches gives * Branch 1 : 2 + 2 = 4 * Branch 2 : 3 + 2 = 5 * Only concerned with branch 2 because branch 1 is LESS than branch 2 hence will fit in the space parallel to branch 2and is available to shrink that much.