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:





Comments

Post a Comment

Popular posts from this blog

Planting flowers with no adjacent flower plots

Image
Problem Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule  Sample inputs  Input: 1,0,0,0,0,0,1,0,0  3 => true  4 => false  Input: 1,0,0,1,0,0,1,0,0  1 => true  2 => false  input: 0  1 => true  2 => false  public boolean canPlaceFlowers(List flowerbed, int numberToPlace) {  // Implementation here  }
Read more
  Given an array of  intervals  where  intervals[i] = [start i , end i ] , merge all overlapping intervals, and return  an array of the non-overlapping intervals that cover all the intervals in the input . Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.   Constraints: 1 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i <= end i <= 10 4
Read more

Find the maximum number of bomb that can be detonated

  Problem You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb. The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range. You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range.  These bombs will further detonate the bombs that lie in their ranges. Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb. Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So...
Read more