Selecting non-overapping ranges from a set of ranges

Question

Selecting non-overapping ranges from a set of ranges

OMG! its sql

SSC Enthusiast

Points: 193
More actions
July 24, 2012 at 12:24 am

#259304

The table contains start and end of the range which can be overlapping. I need a query to return the non-overlapping set of range covering the maximum range.
Table : Ranges
start end
10 20
15 20
25 40
30 40
The output should be
10 20
25 40

Viewing 8 posts - 1 through 8 (of 8 total)

You must be logged in to reply to this topic. Login to reply

Koen Verbeeck SSC Guru Points: 259197 More actions · Answer 1

Try to get your hands on Itzik's book Microsoft SQL Server 2012 High-Performance T-SQL Using Window Functions. It has a few solutions for the "gaps and islands" problem.

Need an answer? No, you need a question
My blog at https://sqlkover.com.
MCSE Business Intelligence - Microsoft Data Platform MVP

Karthiart Ten Centuries Points: 1070 More actions · Answer 2

Hi Below is the query for the scenario which you gave..

select a.start,a.ends from

(select *,

ROW_NUMBER() over (partition by ends order by start asc) Ranking

from ranges)a

where Ranking = 1

Regards,
Karthik.
SQL Developer.

Jeff Moden SSC Guru Points: 1004638 More actions · Answer 3

Karthiart (7/24/2012)
Hi Below is the query for the scenario which you gave..
select a.start,a.ends from
(select *,
ROW_NUMBER() over (partition by ends order by start asc) Ranking
from ranges)a
where Ranking = 1

But it won't handle things like the following which are inevitable for such a thing...

start end

10 15

15 20

25 40

30 40

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Lynn Pettis SSC Guru Points: 442467 More actions · Answer 4

Here is something to start working with to solve your problem.

Read this article, http://www.sqlservercentral.com/articles/T-SQL/71550/, for more insight in to what is happening.

declare @Range table(

[StartRange] int,

[EndRange] int

);

Insert into @Range

Values

(10,20),

(15,20),

(25,40),

(30,40);

select * from @Range;

with

e1(n) as (select 1 from (values (1),(1),(1),(1),(1),(1),(1),(1),(1),(1))dt(n)),

e2(n) as (select 1 from e1 a cross join e1 b),

e4(n) as (select 1 from e2 a cross join e2 b),

tally(n) as (select 0 union all select row_number() over (order by (select null)) from e4 a cross join e2 b),

basedata as (

select distinct

d.StartRange + n as RangeValue

from

@Range d

cross apply (select top (d.EndRange - d.StartRange + 1) n from tally) dt(n)

),

WorkingData as (

select

RangeValue,

row_number() over (order by RangeValue) as rn

from

basedata

)

select

min(RangeValue) as StartRange,

max(RangeValue) as EndRange

from

WorkingData

group by

RangeValue - rn

order by

RangeValue - rn;

go

declare @Range table(

[StartRange] int,

[EndRange] int

);

Insert into @Range

Values

(10,15),

(15,20),

(25,40),

(30,40);

select * from @Range;

with

e1(n) as (select 1 from (values (1),(1),(1),(1),(1),(1),(1),(1),(1),(1))dt(n)),

e2(n) as (select 1 from e1 a cross join e1 b),

e4(n) as (select 1 from e2 a cross join e2 b),

tally(n) as (select 0 union all select row_number() over (order by (select null)) from e4 a cross join e2 b),

basedata as (

select distinct

d.StartRange + n as RangeValue

from

@Range d

cross apply (select top (d.EndRange - d.StartRange + 1) n from tally) dt(n)

),

WorkingData as (

select

RangeValue,

row_number() over (order by RangeValue) as rn

from

basedata

)

select

min(RangeValue) as StartRange,

max(RangeValue) as EndRange

from

WorkingData

group by

RangeValue - rn

order by

RangeValue - rn;

go

Karthiart Ten Centuries Points: 1070 More actions · Answer 5

Jeff Moden (7/24/2012)
Karthiart (7/24/2012)
Hi Below is the query for the scenario which you gave..
select a.start,a.ends from
(select *,
ROW_NUMBER() over (partition by ends order by start asc) Ranking
from ranges)a
where Ranking = 1
But it won't handle things like the following which are inevitable for such a thing...
start end
10 15
15 20
25 40
30 40

That's why i mentioned: "This query is for the scenario which you gave".

But then, i tested the query for your new scenario also. It works properly. Can you please tell me where it fails for the above mentioned request (scenario which you gave).

Regards,
Karthik.
SQL Developer.

Karthiart Ten Centuries Points: 1070 More actions · Answer 6

Karthiart

Ten Centuries

Points: 1070

July 24, 2012 at 12:58 pm

#1517035

Got the Point!!

Regards,
Karthik.
SQL Developer.

Jeff Moden SSC Guru Points: 1004638 More actions · Answer 7

Karthiart (7/24/2012)
Got the Point!!

🙂

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)