Add Interval


  • 0
    W

    This is a design question.
    Write the implementation for the following functions:

    void addInterval(int from, int to)
    int getTotalCoveredLength()
    

    addInterval() adds intervals to an internal structure and getTotalCoveredLength() gets the the total covered length of the intervals, if several intervals intersect, the intersect should only be counted once e.g.

    addInterval(3, 6)
    addInterval(8, 9)
    addInterval(1, 5)
    getTotalCoveredLength() -> 6

    i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6]
    [1,6] and [8,9] don't intersect so total covered length is a sum for both intervals, that is 5 + 1 = 6.

    For addInterval, I was thinking of doing binary insert into a sorted vector of intervals (sorted by from), then before inserting check if overlap with the left or right elements, if we do, merge them, then check the left and right again.

    How would you approach this problem?

    Thanks!


  • 0
    C
    This post is deleted!

  • 0
    O

    Your plan is fine. I merged one direction at a time (merge left until no merge possible, then merge right until no merge possible). I tried using a red black tree (std::set) instead of an array (std::vector) and the array performs slightly better while using less than half the space (no node pointers). I also kept track of the total covered length as the intervals were added/merged so that getTotalCoveredLength runs in O(1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.