Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Disjoint interval unions: maintain covered maintenance time

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A disjoint interval union stores covered time as sorted, nonoverlapping half-open spans [start,end). Adding a window sorts it with the existing spans and merges any overlap or touching boundary. Removing a window preserves unaffected spans and may split one span into two pieces. Membership binary-searches starts, then checks the selected end. The covered length is the sum of each disjoint span width, so overlapping requests count their shared minutes only once. This model stores integral or real time coordinates without time zones; the caller is responsible for converting wall-clock times into a consistent scale.

Operational case

Three maintenance requests [19,47), [61,83), and [47,61) coalesce into [19,83), measuring 64 units. Removing [29,71) leaves [19,29) and [71,83). Time 25 is covered; time 50 is not. The equal boundary at 47 must merge in the add operation, or a supposedly disjoint representation would contain adjacent spans that should form one coverage run. Removing a range outside coverage is harmless. Empty or reversed windows are rejected, because their width and edge semantics would otherwise be unclear.

Working Python program

python
from bisect import bisect_right


class MaintenanceWindows:
    def __init__(self):
        self.windows = []

    def add(self, start, end):
        if start >= end:
            raise ValueError("window must be nonempty")
        merged = []
        for left, right in sorted(self.windows + [(start, end)]):
            if merged and left <= merged[-1][1]:
                previous_left, previous_right = merged[-1]
                merged[-1] = previous_left, max(previous_right, right)
            else:
                merged.append((left, right))
        self.windows = merged

    def remove(self, start, end):
        if start >= end:
            raise ValueError("window must be nonempty")
        surviving = []
        for left, right in self.windows:
            if right <= start or end <= left:
                surviving.append((left, right))
            else:
                if left < start:
                    surviving.append((left, start))
                if end < right:
                    surviving.append((end, right))
        self.windows = surviving

    def contains(self, instant):
        position = bisect_right(self.windows, (instant, float("inf"))) - 1
        return position >= 0 and instant < self.windows[position][1]

    def covered_length(self):
        return sum(right - left for left, right in self.windows)


if __name__ == "__main__":
    schedule = MaintenanceWindows()
    for start, end in [(19, 47), (61, 83), (47, 61)]:
        schedule.add(start, end)
    print(schedule.windows, schedule.covered_length())
    schedule.remove(29, 71)
    print(schedule.windows, schedule.contains(25), schedule.contains(50))

Output

Output
[(19, 83)] 64
[(19, 29), (71, 83)] True False

Time, space, and tradeoff

This direct list model sorts O(R) spans on add, costing O(R log R) time, and scans O(R) spans on removal for R current disjoint runs. A membership query uses O(log R) tuple comparisons; total covered length is O(R) unless maintained as an aggregate during every update. The representation occupies O(R) space and O(R) temporary memory for add or removal. An interval tree answers overlap questions for independent original intervals, while this structure deliberately discards request identity to represent only the union. A balanced ordered map could reduce localized edit costs but needs more machinery.

Common Mistakes

  • Do not count overlapping windows twice when reporting covered duration.
  • Do not treat a half-open right endpoint as covered.
  • Do not forget that removal can split one stored span into two.
  • Do not use this union to recover the identity of every original request.

Connected lessons

Compare its input and update contract with X-fast trie: predecessor and successor in a fixed integer universe, Persistent radix vectors: copy one indexed path per revision, Compressed suffix trees: locate patterns across a frozen text, then complete the structure audit and decision quiz.

Segment-tree stabbing indexes: list intervals active at one point adds a related structure with a different operation boundary.

Run-length bitmaps: union, intersect, and subtract alert spans adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details