recursion - 合并 2 组间隔

Question

我有一个联合方法设置来组合两组有序间隔:

(define (union set1 set2)
  (cond [(empty? set1) set2]
        [(empty? set2) set1]
        [(< (caar set1) (caar set2)) (cons (car set1) (union (cdr set1)
                                                             set2))]
        [else (cons (car set2) (union set1
                                      (cdr set2)))]))

给定 2 个列表 '((1 3) (5 10) (19 29)) 和 '((2 4) (17 25) (30 49)) 他们生产

'((1 3) (2 4) (5 10) (17 25) (19 29) (30 49)) 与上面的代码。

但是通过上述实现，重叠间隔没有得到正确处理。我需要合并重叠间隔以生成 '((1 3) (2 4) (5 10) (17 29) (30 49))。我该如何处理这些间隔合并以避免重叠？

Answer 1

假设您使用半开区间[from upto)，Racket 提供 interval-map模块:

An interval-map is a mutable data structure that maps half-open intervals of exact integers to values. An interval-map is queried at a discrete point, and the result of the query is the value mapped to the interval containing the point.

提供的示例:

> (define r (make-interval-map))
> (interval-map-set! r 1 5 'apple)
> (interval-map-set! r 6 10 'pear)
> (interval-map-set! r 3 7 'banana)
> (dict-map r list)
'(((1 . 3) apple) ((3 . 7) banana) ((7 . 10) pear))

使用示例输入 '((1 3) (5 10) (19 29)) 和 '((2 4) (17 25) (30 49)):

#lang racket/base
(require data/interval-map
         racket/list
         racket/match
         racket/dict)

(define im (make-interval-map))

;; Add your first set
(for ([x '((1 3) (5 10) (19 29))])
  (interval-map-set! im (first x) (second x) #f))

;; Add your second set
(for ([x '((2 4) (17 25) (30 49))])
  (interval-map-set! im (first x) (second x) #f))

;; The result
(map car (dict-map im list))
;; => '((1 . 2) (2 . 4) (5 . 10) (17 . 25) (25 . 29) (30 . 49))