Page 1 of 3 123 LastLast
Results 1 to 15 of 44
  1. #1
    Join Date
    Jul 2004
    Posts
    53

    Unanswered: Overlapping integer ranges ??

    Dont know if this will be tough for the rest of you but for someone who is fairly new to SQL...I cannot figure it out...

    I have a table:

    Rownumber starttime endtime
    1 l 30 l 240
    2 l 40 l 120
    3 l 50 l 260
    4 l 1300 l 1400



    Rows 1, 2, and 3 over lap with one another and I am trying to obtain the starttime and endtime values which can cover them all.

    I would like to find the overlapping (starttime - endtime) ranges and accept the lowest starttime value and the highest endtime value.

    Row 1: 30--------------------240
    Row 2: 40--------------120
    Row 3: 50----------------------260
    Row 4: ...1300---------1440


    I would like to include starttime-endtime ranges that do not overlap with any other integer range.

    which in this case would be:

    Rownumber starttime endtime
    1 l 30 l 260
    2 l 1330 l 1400


    I was thinking of using a cursor and comparing each row to all of the other rows in the table and then setting a boolean in that row if it overlaps with another row in the table...is there a better way of doing this?

    Thank you for the help!

  2. #2
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    yes, there is a better way

    "comparing each row to all of the other rows in the table" is as good a definition of a self-crossjoin as i can think of

    a self-crossjoin would be written like this:
    Code:
    select t1.rownumber 
         , t1.starttime 
         , t1.endtime 
         , t2.rownumber 
         , t2.starttime 
         , t2.endtime 
      from yourtable as t1
    cross
      join yourtable as t2
    now, with this as the basis, you can add a WHERE condition for overlapping ranges

    e.g. WHERE t1.starttime BETWEEN t2.starttime and t2.endtime

    you'd want to be careful about which pairs you want to keep, which would basically be the same idea as your "setting a boolean in that row if it overlaps" except that instead of setting a boolean, the t1 row survives the WHERE filter

    make sense?
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  3. #3
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    What defines an "overlap" for your case? Some overlaps are obvious, since the beginning of one range sits inside of another, but what about more complex cases like:

    1 50 250
    2 200 450
    3 300 650
    4 500 800

    Is this one range, two ranges, or something different?

    -PatP

  4. #4
    Join Date
    Jul 2003
    Location
    San Antonio, TX
    Posts
    3,662
    I'd think the poster would want this as a result based on Pat's example:

    1 50 450
    4 500 800

    Is my assumption correct?
    "The data in a record depends on the Key to the record, the Whole Key, and
    nothing but the Key, so help me Codd."

  5. #5
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    I'm just curious, but how the heck did you get there? That was a combination that I never thought of!

    -PatP

  6. #6
    Join Date
    Jul 2004
    Posts
    53
    rdjabarov: You're close but the I am looking for only 50-800 (u can the view diagram below)

    PatP: if that question was posed to me, this table is storing a list of times that are blocked off for the a day (i.e. hotel reservations, someone's personal schedule). (BUT Times can overlap in this case). So from the table of overlapping ( or non-overlapping) times (int), I need to find the times where either the entire range or part of the range sit inside another time.

    i.e.

    1 50 250 ---entire range sits inside 2
    2 200 450 ---entire range sits inside 3
    3 300 650 --part of this range (500-650) overlaps with 4
    4 500 800 --and accordingly, (500-650) overlaps with 3

    This is what I use to visualize it (where -------- is a blocked off time):

    For Date 07-26-2004:

    0 1000

    ........... 50-----------------------250
    ................................. 200----------------450 <sp>
    ..........................................300--------------------650
    .................................................. .......... 500---------------800

    so 50-800 would be the time range that would encompass all of the other time ranges since each one overlaps with another...


    r937, thank you for your suggestion

    not even sure how to begin with the where statement to achieve the above

    is the select syntax supposed to be?:
    select t1.rownumber
    , t1.starttime
    , t1.endtime
    , t2.rownumber
    , t2.starttime
    , t2.endtime
    from yourtable as t1
    cross
    join yourtable as t2
    where t1.Rownumber = t2.rownumber

    cause when I do just what you suggested (without the where t1.Rownumber = t2.rownumber)

    I get:

    Rownumber starttime endtime Rownumber starttime endtime
    1 l 30 l 240 1 l 30 l 240
    2 l 40 l 120 1 l 30 l 240
    3 l 50 l 260 1 l 30 l 240
    4 l 1300 l 1400 1 l 30 l 240
    1 l 30 l 240 2 l 40 l 120
    2 l 40 l 120 2 l 40 l 120
    3 l 50 l 260 2 l 40 l 120
    4 l 1300 l 1400 2 l 40 l 120
    1 l 30 l 240 3 l 50 l 260
    2 l 40 l 120 3 l 50 l 260
    3 l 50 l 260 3 l 50 l 260
    4 l 1300 l 1400 3 l 50 l 260
    1 l 30 l 240 4 l 1300 l 1400
    2 l 40 l 120 4 l 1300 l 1400
    3 l 50 l 260 4 l 1300 l 1400
    4 l 1300 l 1400 4 l 1300 l 1400

  7. #7
    Join Date
    Jul 2003
    Location
    San Antonio, TX
    Posts
    3,662
    Hmmmm...Any previous maximum endtime should be less than any consecutive minimum starttime...I think...Isn't it? But now that I am looking at it, if that's the logic then the only result you can get from Pat's example would be:

    1 50 800
    "The data in a record depends on the Key to the record, the Whole Key, and
    nothing but the Key, so help me Codd."

  8. #8
    Join Date
    Jul 2003
    Location
    San Antonio, TX
    Posts
    3,662
    Hey, you beat me to that, that's what I thought. Now the question is how to take into account ranges that DON'T overlap, because if you just do MIN(starttime) and MAX(endtime) it would skip non-overlapping ranges.
    "The data in a record depends on the Key to the record, the Whole Key, and
    nothing but the Key, so help me Codd."

  9. #9
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    awfdml, the first thing you should do is restate your requirements

    a precise statement of requirements is crucial

    for example, your first post said "I am trying to obtain the starttime and endtime values which can cover them all"

    which can cover them all suggests that MIN() and MAX() is sufficient

    but there will be holes, right?

    and if you somehow want to see the holes....?

    try to give a statement which defines all the start/end pairs you want
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  10. #10
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    The real problem comes from sequences like:

    10-30
    30-50
    50-70
    70-90
    90-110
    110-130
    130-150
    etc.

    Each trip through the consolidation process brings new consolidations. I don't know of a way to express this using set notation without using iteration, so I think that you'll have to use an iterative (code based) solution.

    At least in SQL-2000 you could solve the problem using a table valued function.

    -PatP

  11. #11
    Join Date
    Jul 2004
    Posts
    53
    Pat: With the scenario you suggested, I would still consider each one overlapping since they share the sametimes

    i.e. 10-30 (30 is shared, 50 is shared)...therefore the result would be 10-70
    30-50
    50-70

    Think this would be what you're telling me, Pat?

    30-50
    40-60
    50-70
    90-110
    110-120

    30---50
    .....40-----60
    .......50--------70
    .............................90----------110
    ..............................................110------------120

    rdjabarov: I think the problem with doing a min and max is in the above scenario, like u stated

    The result I would need to achieve in this case is:

    First 3 times overlap with one another (one set), Last two overlap (second set) (but there is no overlap between)

    30-70
    90-120

    r937: Yes, there will be holes (like above)

    I definitely apologize if I did not clarify what I am looking for but I shall try

    For a given table of blocked times, find all of the ranges(start-end) that overlap (partly, or entirely).

    For each set of overlapping ranges, return* the range that will encompass the set.

    If a range of the blocked times do not overlap with any another, return the the range.

    *return-meaning store into a temp table or return as resultset

    I.E.

    Scenario 1: All ranges overlap

    10-30
    30-60
    50-70
    70-90

    Result : 10-90


    Scenario 2: Some ranges overlap with others, or not at all

    20-40
    35-55
    40-60
    70-90
    85-100
    150-200


    Result: 20-60
    70-100
    150-200


    Scenario 3: None of the times overlap

    100-150
    180-200
    250-300


    Result: 100-150
    180-200
    250-300

    I am hoping that I do not have to use an iterative solution. (me in denial )

    The list of blocked times will not be big at all (most it could possibly be is 60 (per minute and NOT realistic)
    For my case, the largest list of blocked times I would get could be anywhere from 12-20.

    Still open to any suggestions of course as I think away Thank you all for your suggestions thus far!

  12. #12
    Join Date
    Jul 2004
    Posts
    53
    Forgot to ask Pat:

    "At least in SQL-2000 you could solve the problem using a table valued function."

    I am using SQL 2000, and this probably is a stupid question but what is a "table valued" function? Is it the user defined function?



    Thanks!

  13. #13
    Join Date
    Jul 2003
    Location
    San Antonio, TX
    Posts
    3,662
    Check UDF in BOL.
    "The data in a record depends on the Key to the record, the Whole Key, and
    nothing but the Key, so help me Codd."

  14. #14
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    In SQL-2000, User Defined Functions come in two flavors. Scalar functions return a single value, much like a C function would and are used anywhere an rvalue can be used like the SELECT list the WHERE clause, etc. Table valued functions actually return a table as their value and are used in the FROM clause almost exactly like you'd use a table.

    -PatP

  15. #15
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    just a dumb question, but what are your units?

    your scenarios all use 20, 30, 55, etc.

    is 1 the smallest unit here? perhaps 5? these are minutes, right?

    because you did mention these were times, and i notice the largest value you're using is 1440 (which should be familiar to anyone who has ever worked with date and time values)
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •