## Overlap

### June 8, 2018

A little bit of thinking (and a few trials when I thought backwards) gives this solution:

```(define (overlap xlo xhi ylo yhi)
(if (or (< xhi ylo) (< yhi xlo)) '()
(list (max xlo ylo) (min xhi yhi))))```

If an overlap exists, it starts at the maximum of the `lo` values and ends at the minimum of the `hi` values. Here are some examples:

```> (overlap 17 25 12 19)
(17 19)
> (overlap 12 17 19 25)
()
> (overlap 19 25 12 17)
()
> (overlap 19 25 22 30)
(22 25)```

You can run the program at https://ideone.com/c7a0XU.

Pages: 1 2

### 9 Responses to “Overlap”

1. V said

In Ruby. Using Ranges (built-in)

```def overlap(a, b)
o = a.to_a & b.to_a
o.size < 2 ? nil : (o.first..o.last)
end

# Test
puts overlap((19..25), (22..30))
puts overlap((19..25), (12..17)).inspect
```

Outout:

22..25
nil

2. Daniel said

Here’s a solution in C.

```#include <stdio.h>
#include <stdlib.h>

void print_usage_and_exit(char* prog) {
fprintf(stderr, "Usage: %s min1 max1 min2 max2\n", prog);
exit(EXIT_FAILURE);
}

int main(int argc, char* argv[]) {
if (argc != 5) {
print_usage_and_exit(argv);
}
int min1 = atoi(argv);
int max1 = atoi(argv);
int min2 = atoi(argv);
int max2 = atoi(argv);
if (max1 < min1 || max2 < min2) {
print_usage_and_exit(argv);
}
if (min1 <= max2 && max1 >= min2) {
int min3 = min1 > min2 ? min1 : min2;
int max3 = max1 < max2 ? max1 : max2;
printf("%d %d\n", min3, max3);
}
return EXIT_SUCCESS;
}
```

Example:

```\$ ./overlap 17 25 12 19
17 19

\$ ./overlap 12 17 19 25

\$ ./overlap 19 25 12 17

\$ ./overlap 19 25 22 30
22 25
```
3. Globules said

A Haskell version. For clarity we create a type for ranges.

```data Range a = R a a | Empty deriving (Show)

mkRange :: Ord a => a -> a -> Range a
mkRange x y | x <= y    = R x y
| otherwise = Empty

overlap :: Ord a => Range a -> Range a -> Range a
overlap (R x1 y1) (R x2 y2) = let (x, y) = (max x1 x2, min y1 y2)
in if x <= y then R x y else Empty
overlap _         _         = Empty

main :: IO ()
main = do
print \$ overlap (mkRange 19 25) (mkRange 22 30)
print \$ overlap (mkRange 19 25) (mkRange 12 17)

print \$ overlap (mkRange 'k' 'o') (mkRange 'a' 'm')
```
```\$ ./overlap
R 22 25
Empty
R 'k' 'm'
```
4. Milbrae said

Python

```def overlap(a_min, a_max, b_min, b_max):
''
return list(sorted(set(range(a_min, a_max+1)) & set(range(b_min, b_max+1))))

if __name__ == "__main__":
''
print (overlap(19, 25, 22, 30))
print (overlap(12, 17, 19, 25))
```

[22, 23, 24, 25]
[]

5. thebillywayne said
```> def does_overlap(a, b, c, d):
overlap = set(range(a, b+1)).intersection(set(range(c, d+1)))
print(sorted(overlap)) if overlap else print("No overlap")
```
```> does_overlap(19, 25, 22, 30)
[22, 23, 24, 25]
> does_overlap(19, 25, 12, 17)
"No overlap"
```
6. Daniel said

Here’s a solution in Python.

```def overlap(min1, max1, min2, max2):
if min1 <= max2 and max1 >= min2:
return max(min1, min2), min(max1, max2)
return None

print(overlap(17, 25, 12, 19))
print(overlap(12, 17, 19, 25))
print(overlap(19, 25, 12, 17))
print(overlap(19, 25, 22, 30))
```

Output:

```(17, 19)
None
None
(22, 25)
```
7. Steve said

Mumps version

```JSG	;
Q
;
PAIRS(X1,X2)	;
N A,B,I,MAXA,MINB,VAR
F I=1,2 S VAR="X"_I,A(I)=\$P(@VAR,","),B(I)=\$P(@VAR,",",2)
S MAXA=\$S(A(1)>A(2):A(1),1:A(2)),MINB=\$S(B(1)<B(2):B(1),1:B(2))
Q \$S(MAXA>MINB:"",1:MAXA_","_MINB)
vista@steve-VirtualBox:~/EHR/r\$ gtm

GTM>S X1="19,25" F X2="22,30","1,18","26,30","10,23","19,25","19,30","18,26","20,25","20,30" W !,X1," & ",X2," --> ",\$\$PAIRS^JSG(X1,X2)

19,25 & 22,30 --> 22,25
19,25 & 1,18 -->
19,25 & 26,30 -->
19,25 & 10,23 --> 19,23
19,25 & 19,25 --> 19,25
19,25 & 19,30 --> 19,25
19,25 & 18,26 --> 19,25
19,25 & 20,25 --> 20,25
19,25 & 20,30 --> 20,25
GTM>
```
8. Klong version

```
pairs::{[a b]; a::(x@0)|(y@0); b::(x@1)&(y@1); :[b<a; []; a,b]}
pairs([1 18]; [19 25])
[]
pairs([1 19]; [19 25])
[19 19]
pairs([1 20]; [19 25])
[19 20]
pairs([19 20]; [19 25])
[19 20]
pairs([20 20]; [19 25])
[20 20]
pairs([20 24]; [19 25])
[20 24]
pairs([20 25]; [19 25])
[20 25]
pairs([20 26]; [19 25])
[20 25]
pairs([24 26]; [19 25])
[24 25]
pairs([25 26]; [19 25])
[25 25]
pairs([26 26]; [19 25])
[]

```
9. Kevin said

racket version

```(define (overlap a b)
(cond
[(and (empty? a) (empty? b)) empty]
[(or (empty? a) (empty? b)) 'NoOverlap]
[else
(let* ((x (if (< (car a) (car b)) a b)) (y (if (equal? x a) b a)))
(if (> (car y) (cadr x))
'NoOverlap
```

Testing

```(overlap '() '()) ==> '()
(overlap '() '(22 30)) ==> 'NoOverlap
(overlap '(22 30) '()) ==> 'NoOverlap
(overlap '(19 25) '(22 30)) ==> '(22 25)
(overlap '(22 30) '(19 25)) ==> '(22 25)
(overlap '(10 30) '(12 22)) ==> '(12 22)
(overlap '(12 22) '(10 30)) ==> '(12 22)
(overlap '(19 25) '(12 17)) ==> 'NoOverlap
(overlap '(12 17) '(19 25)) ==> 'NoOverlap
```