Efficient way to combine intersecting bounding rectangles

Efficient way to combine intersecting bounding rectangles

I'm trying to simplify the following image using OpenCV:

What we have here is lots of red shapes. Some of them completely contain
others. Some of them intersect their neighbors. My goal is to unify all
intersecting shapes by replacing any two intersecting shapes with the
bounding box of their union's polygon. (repeating until there are no more
intersecting shapes).
By intersecting I mean also touching. Hope this makes it 100% clear:

I'm trying to do this efficiently using standard morphology operations;
obviously it can be done naively in O(N^2), but that'll be too slow.
Dilation doesn't help because some shapes are only 1px apart and I don't
want them merged if they're not intersecting.