Getting the total covered length given the interval

Problem

Write the program that takes the series of intervals and returns a total length covered by the added intervals.

 If several intervals intersect, the intersection should be counted only once.

 Example:

 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 the total covered length is a sum of both intervals, that is 5+1=6.

                   ______

                                       _

          _________

  
      0  1  2  3  4  5  6  7  8  9  10

    
Now, implement the following two methods.

     

public:

    void addInterval(int from, int to)

    {

        // implement the methods

    }

    int getTotalCoveredLength()

    {

    }

Brute-force approach, $O(N^2)$

Simplest approach is to compare new intervals with the existing intervals and merge the intervals if a new interval overlaps with any existing ones.

This approach achieves the following time complexity.

addInterval(), $O(N^2)$ 
   To examine the N existing intervals each time. We also update the total covered intervals during the addition process.

getTotalCoveredLength(), $O(1)$
   To return the total covered interval.

More efficient approach with the binary tree,  $O( \log N)$

Instead of keeping the list of intervals, we can keep the in the binary tree sorted by "end" of intervals.
This algorithm can reduce the pervious $O(N^2)$ time into $O(\log N)$ through the binary search.

For the optimal performance, we could implement the balancing routine to keep the heigh of the tree O(\log N). However, the interview would not expect you to implement that during the interview.

Here is the complete code of the binary tree approach.

Practice statistics:

5:00: to think up the algorithm

29:14: write up the code and test cases (one minor typo)

Less efficient approach with MinHeap,  $O( N \log N)$

Another way to solve this problem is to use MinHeap to keep the sorted range.

addInterval(), $O(log N)$

  Adding a new interval to heap is $O(log N)$.

getTotalCoveredLength(), $O(N log N)$

To calculate the covered length, we can extract elements from MinHeap and merge intervals.

Since MinHeap sorts intervals by start value, we can merge intervals or adds the length of intervals to the sum.

Extract() method of MinHeap takes $O(log N)$. Therefore iterating over N intervals will take $O(N log N)$.

Here is python solution: