Find all combinations of non overlapping intervals

Transact-SQL
1

Hi there

I have a table of intervals for example

Start, end
1,8
2,13
9, 18
15, 30
20, 35

I need to be able return all of the non overlapping combinations of these so the result would be

[20,35]
[15,30]
[9,18]
[9,18][20,35]
[2,13]
[2,13][20,35]
[2,13][15,30]
[1,8]
[1,8][20,35]
[1,8][15,30]
[1,8][9,18]
[1,8][9,18][20,35]

I do have a way by creating the Cartesian product of combinations first but I'm hoping there is a better was as when I need to do the same thing for a larger table of intervals the Cartesian combination becomes way too large.

Any advice very welcome

Thanks

2

I don't believe there is a way you can avoid the cartesian product(s), especially since you want ALL combinations that don't overlap. That's not something that SQL is designed for. It's possible that you could call a Python library via the machine learning feature in SQL Server 2017 or higher that has optimizations for this kind of processing.

If you happened to have 100 segments that don't overlap, you'd have to recurse at least 100 times in SQL to get them all, there's no magic available that I can think of. The craziest idea I have is to generate Geometry objects and use the STIntersects method to find overlaps:

And that will almost certainly run very very slowly, and won't avoid recursing over all combinations.

This kind of thing would probably run best via GPU coding, you'd simply dump all the coordinates from the database into GPU RAM and run optimized code on it.

1 Like