El Blog de Trespams

Avui em fa ganes dedicar un parell de línies a tractar un problema força comú que ens trobam amb programació. A saber, la necessitat de saber si dos intervals solapen o no.

El problema es pot presentar en diverses formes, però un cas força típic és el que tenim una taula que conté una data inicial i una data final i ens demanen que a partir d'un rang de dades, trobem tots els registres que tenen dades compreses entre les donades. Un cas molt típic es del de tenir un preu d'oferta que es vàlid per un rang de dades concret.

Anem a concretar el problema. Tenim un producte que presenta ofertes. Pels qui feis feina al sector turístic això us pot sonar als preus d'un hotel, però el problema és prou genèric, com diuen els matemàtics, podem considerar sense pèrdua de generalitat que tenim una sèrie de dies en que tenim ofertes i promocions de productes

dia descompte 1-8 10 € 9-10 20 € 11-25 15 € 25-31 5 €

El nostre client ens demana un rang de dies i volem donar-li quines ofertes hi ha actives per aquests dies

10 -> 20 11 -> 15 12 -> 15

és a dir, li diríem que hi ha dues ofertes dins el rang cercat, una que correspon a l'interval 9-10 i l'altra a l'interval 11-25

El problema es redueix a determinar quins intervals del nostre rang de consulta solapen amb l'interval d'ofertes i mostrar l'oferta corresponent.

El mètode més directe per comprovar si dos intervals es trepitgen és mirar-ne les condicions en que es solapen, suposant que anomenam a l'interval base [x0,x1] i a l'interval de comprovacio [y0, y1] tendríen que es dona solapament en aquests casos

[yyy] [xxxxxxxxxx] cas 1 x0>=y0 and y1<=x1 [yyy] [xxxxxxxx] cas 2 y1>=x0 and y0<=x0 [yyyyy] [xxxxxxxxxx] cas 3 y0<=x1 and y1>x1 [yyyyyyyyyyy] [xxx] cas 4 x0>=y0 and x1<=y1 [yyyyyyyy] [xxxxx] cas 5 x0<=y1 and y1<x1 | y0 | y1 | x0 | x1 | cas | | 10 | 12 | 1 | 8 | - | | 10 | 12 | 9 | 10 | 3 | | 10 | 12 | 11 | 25 | 2 | | 10 | 12 | 25 | 31 | - |

Si ajuntam casos semblants el codi que tindrem és

def overlaps(x, y):
    x0, x1 = x
    y0, y1,preu = y
    return ((x0 <= y0 <= x1) or (x0 <= y1 <= x1) or (y0 <= x0 <= y1) or (y0 <= x1 <= y1))

Però el més interessant és que ho podem pensar d'una altra manera, pensem en la inversa, demanem-nos quan els intervals no és solapen

[xxxxxxx] [yyyyyyyyyy] [yyyyyyy] [xxxxxxxxx]

és a dir, dos intervals no és solapem si x1<y0 o bé y2<x0, podem cercar dons quan no no es solapen els intervals, i per tant tindrem not (x1<y0) or (y1<x0)

def overlaps2(x, y):
    x0, x1 = x
    y0, y1, preu = y
    return not ((x1<y0) or (y1<x0))

divertit, veritat?