Have you tried a 1-d kd tree, that at each subinterval keeps track of the largest gap? Should be fairly simple to keep this updated and effectively match/genera

Have you tried a 1-d kd tree, that at each subinterval keeps track of the largest gap? Should be fairly simple to keep this updated and effectively match/generalize your "coalescing" logic.