Interval List Intersections — Flow Diagram — Data Structures & Algorithms

Interval List Intersections — control flow

flowchart TD
    S["<b>i · init</b><br/>i = 0; j = 0; result = []"]
      --> L{"<b>ii · both in range?</b><br/>i &lt; len(A) and j &lt; len(B)"}
    L -->|"yes"| X["<b>iii · candidate</b><br/>lo = max(A[i][0], B[j][0])<br/>hi = min(A[i][1], B[j][1])"]
      --> V{"<b>iv · valid?</b><br/>lo ≤ hi?"}
    V -->|"yes"| P["<b>v · record</b><br/>result.append([lo, hi])"]
      --> A{"<b>vi · which ends first?</b>"}
    V -->|"no"| A
    A -->|"A[i][1] &lt; B[j][1]"| IA["<b>vii · i++</b>"]
    A -->|"else"| IJ["<b>viii · j++</b>"]
    IA --> L
    IJ --> L
    L -->|"no"| R["<b>return</b> result"]
 
    classDef start fill:#f5efe1,stroke:#6a8a4f,stroke-width:2px,color:#1a1915;
    classDef decision fill:#fdecd3,stroke:#c2410c,stroke-width:2px,color:#1a1915;
    classDef action fill:#e7efd9,stroke:#587640,stroke-width:2px,color:#1a1915;
    class S start
    class L,V,A decision
    class X,P,IA,IJ,R action

Initialise

Two pointers at 0, empty result list.
Loop guard

Continue while both lists still have intervals.
Candidate

`lo = max(starts)`, `hi = min(ends)` — the overlap formula.
Validity

`lo ≤ hi` → real intersection; otherwise the intervals don’t overlap.
Record

Push `[lo, hi]` onto the result.
Which ends first

The interval with the smaller end time cannot intersect anything else from the other list — drop it.
Advance A

`i++` when `A[i][1] < B[j][1]`.
Advance B

`j++` otherwise (including ties).

Interval List Intersections — control flow

Comments