Structure

BST keyed by interval start. Each node stores max end in its subtree.

Advertisement

Overlap query

void query(Node n, int qLow, int qHigh, List result) {
  if (n == null) return;
  if (n.interval.high < qLow || n.interval.low > qHigh) {
    // no overlap with n itself
  } else result.add(n.interval);
  // Only descend left if left's max end >= qLow
  if (n.left != null && n.left.maxEnd >= qLow) query(n.left, qLow, qHigh, result);
  if (n.interval.low <= qHigh) query(n.right, qLow, qHigh, result);
}
Advertisement

Balancing

Use AVL or red-black tree as backbone. Maintain maxEnd on rotations.

Applications

Calendar systems (find all events in day). Genomics (overlapping genes). Range scheduling.