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.

	#include<iostream>
	using namespace std;
	struct node {
	int start;
	int end;
	int length;
	node* left;
	node* right;
	node(int s, int e) :start(s), end(e), left(0), right(0)
	{
	length = e - s;
	}
	};
	class Range
	{
	private:
	int total;
	node* root;
	bool isOverlap(node * cur, int from, int to)
	{
	return (cur->end >= from && cur->start <= to);
	}
	public:
	Range() :total(0), root(0){}
	void addInterval(int from, int to)
	{
	if (!root)
	{
	root = new node(from, to);
	total = root->length;
	return;
	}
	bool isLeft = false;
	node* parent = 0;
	node * cur = root;
	while (cur)
	{
	if (isOverlap(cur, from, to))
	{
	total -= cur->length;
	int s = (cur->start > from) ? from : cur->start;
	int e = (cur->end < to) ? to : cur->end;
	cur->start = s;
	cur->end = e;
	cur->length = e - s;
	total += cur->length;
	return;
	}
	else if (cur->end > to)
	{
	isLeft = true;
	parent = cur;
	cur = cur->left;
	}
	else {
	isLeft = false;
	parent = cur;
	cur = cur->right;
	}
	}
	if (parent)
	{
	node * leaf = new node(from, to);
	if (isLeft)
	parent->left = leaf;
	else
	parent->right = leaf;
	total += leaf->length;
	}
	}
	int getTotalCoveredLength()
	{
	return total;
	}
	};
	int main()
	{
	Range tree;
	tree.addInterval(3, 6);
	cout << " total = " << tree.getTotalCoveredLength() << endl;
	tree.addInterval(8, 9);
	cout << " total = " << tree.getTotalCoveredLength() << endl;
	tree.addInterval(1, 5);
	cout << " total = " << tree.getTotalCoveredLength() << endl;
	tree.addInterval(7, 12);
	cout << " total = " << tree.getTotalCoveredLength() << endl;
	tree.addInterval(2, 4);
	cout << " total = " << tree.getTotalCoveredLength() << endl;
	tree.addInterval(13, 14);
	cout << " total = " << tree.getTotalCoveredLength() << endl;
	return 1;
	}

view raw range_tree.cpp hosted with ❤ by GitHub

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:

	import math
	class Interval:
	def __init__(self, start, end):
	self.start = start
	self.end = end
	def length(self):
	return self.end - self.start
	class MinHeap:
	def __init__(self):
	self.nodes = []
	self.nodes.append(Interval(None,None))
	def extract(self):
	if len(self.nodes) <= 1:
	return None
	value = self.nodes[1]
	self.swap(1, len(self.nodes)-1)
	self.nodes.pop()
	self.bubbleDown(1)
	return value
	def insert(self, value):
	self.nodes.append(value)
	self.bubbleUp(len(self.nodes)-1)
	def left(self, parent):
	return 2*parent
	def right(self, parent):
	return 2*parent + 1
	def parent(self, child):
	return int(math.floor(child/2))
	def swap(self, l, r):
	temp = self.nodes[l]
	self.nodes[l] = self.nodes[r]
	self.nodes[r] = temp
	def bubbleUp(self, child):
	if child <= 1:
	return
	p = self.parent(child)
	if self.isChild(p, child) != True:
	self.swap(p, child)
	self.bubbleUp(p)
	def bubbleDown(self, parent):
	if parent >= len(self.nodes) -1:
	return
	lpos = self.left(parent)
	if lpos >= len(self.nodes) -1:
	return
	rpos = self.right(parent)
	swap_value = lpos if rpos >= len(self.nodes) -1 or self.isChild(lpos, rpos) == True else rpos
	if self.isChild(parent, swap_value) != True:
	self.swap(parent, swap_value)
	self.bubbleDown(swap_value)
	def isChild(self, parent, child):
	return self.nodes[parent].start < self.nodes[child].start
	class MergeInterval:
	def __init__(self):
	self.heap = MinHeap()
	# O(Log N)
	def addInterval(self, start, end):
	interval = Interval(start, end)
	self.heap.insert(interval)
	# O(N log N)
	def getTotalCoveredLength(self):
	newHeap = MinHeap()
	cur = self.heap.extract()
	prev = None
	sum = 0
	while (cur != None):
	if prev != None:
	if self.notOverlap(prev, cur) != True:
	new_start = min(prev.start, cur.start)
	new_end = max(prev.end, cur.end)
	prev = Interval(new_start, new_end)
	else:
	sum += prev.length()
	newHeap.insert(prev)
	prev = cur
	else:
	prev = cur
	cur = self.heap.extract()
	if prev != None:
	sum += prev.length()
	newHeap.insert(prev)
	self.heap = newHeap
	return sum
	def notOverlap(self, prev, next):
	return prev.end < next.start or next.end < prev.start
	m = MergeInterval()
	m.addInterval(3, 6)
	m.addInterval(8, 9)
	m.addInterval(1, 5)
	print ('answer = {}'.format(m.getTotalCoveredLength()))

view raw get_merged_intervals.py hosted with ❤ by GitHub