#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/stabbing-number-problem

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/stabbing-number-problem

Repovive

Stabbing Number Problem - Interval Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Stabbing Number Problem

Max coverage point

Given intervals, find the point covered by the maximum number of intervals.

function maxStabbingPoint(intervals)
    events := []
    for interval in intervals
        events.add((interval.low, +1))
        events.add((interval.high + 1, -1))

    sort events by position

    maxCount := 0
    count := 0
    bestPoint := null

    for (pos, delta) in events
        count := count + delta
        if count > maxCount then
            maxCount := count
            bestPoint := pos

    return bestPoint

The +1 offset on high ensures we count endpoints correctly for closed intervals.

Time: $O(n \log n)$ . Space: $O(n)$ .