Interval Search Tree

Problem 

Discuss Interval Search Tree

Idea behind Interval Search Tree
Lets discuss the 1D Interval search. By 1D I mean in 1 dimension i.e. having interval along 1 axis only. So, suppose along x axis we have collection of intervals - [1,2], [1,3] and so on.

Here Interval Tree or Interval Search tree is helpful as it holds set of (overlapping) intervals

• Insert the interval
• Search
• delete
• Main functionality - Interval intersection query - given the interval (lo, hi) find all intervals in data structure which intersect with given interval.

 Data structure for IST
Interval Tree: The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc to maintain set of intervals so that all operations can be done in O(Logn) time.
Every node of Interval Tree stores following information.

1. i: An interval which is represented as a pair [low, high]
2. max: Maximum high value in subtree rooted with this node.

The low value of an interval is used as key to maintain order in BST. The insert and delete operations are same as insert and delete in self-balancing BST used.

Here is the java data structure for Node :

private class Node {
    Interval1D interval;      // key
    Value value;              // associated data
    Node left, right;         // left and right subtrees
    int N;                    // size of subtree rooted at this node
    int max;                  // max endpoint in subtree rooted at this node

    Node(Interval1D interval, Value value) {
        this.interval = interval;
        this.value    = value;
        this.N        = 1;
        this.max      = interval.high;
    }
}

Here is how the basic structure of interval search tree looks:

public class Interval1D implements Comparable<Interval1D> {
    public final int low;   // left endpoint
    public final int high;  // right endpoint
}

The main operation is to search for an overlapping interval. Following is algorithm for searching an overlapping interval x in an Interval tree rooted with root.

Interval overlappingIntervalSearch(root, x)
1) If x overlaps with root's interval, return the root's interval.

2) If left child of root is not empty and the max  in left child 
    is greater than x's low value, recur for left child

3) Else recur for right child.

Example
Consider x = [6,7]. We see if x overlaps with root [15,20]. Answer is no. Now we check if max of left child i.e. 30 greater than x's low value i.e. 6. If yes, we move to left node. Likewise we continue, and find out interval in the tree is [5,20].

How does the above algorithm work?
Let the interval to be searched be x. We need to prove this in for following two cases.
Case 1: When we go to right subtree, one of the following must be true.
a) There is an overlap in right subtree: This is fine as we need to return one overlapping interval.
b) There is no overlap in either subtree: We go to right subtree only when either left is NULL or maximum value in left is smaller than x.low. So the interval cannot be present in left subtree.
Case 2: When we go to left subtree, one of the following must be true.
a) There is an overlap in left subtree: This is fine as we need to return one overlapping interval.
b) There is no overlap in either subtree: This is the most important part. We need to consider following facts.
… We went to left subtree because x.low <= max in left subtree
…. max in left subtree is a high of one of the intervals let us say [a, max] in left subtree.
…. Since x doesn’t overlap with any node in left subtree x.low must be smaller than ‘a‘.
…. All nodes in BST are ordered by low value, so all nodes in right subtree must have low value greater than ‘a‘.
…. From above two facts, we can say all intervals in right subtree have low value greater than x.low. So x cannot overlap with any interval in right subtree.

Implementation of Interval Tree
The code here will be too long. I have put this class in github. You may refer to Interval1D class here.

Please feel free to comment if you have any suggestions. 

Applications of Interval Tree:
Interval tree is mainly a geometric data structure and often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene (Source Wiki).

Interval Tree vs Segment Tree
Both segment and interval trees store intervals. Segment tree is mainly optimized for queries for a given point, and interval trees are mainly optimized for overlapping queries for a given interval. More here.


References
http://en.wikipedia.org/wiki/Interval_tree
http://algs4.cs.princeton.edu/92search/
http://algs4.cs.princeton.edu/93intersection/IntervalST.java.html
http://algs4.cs.princeton.edu/93intersection/
http://www.geeksforgeeks.org/interval-tree/
Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
https://www.youtube.com/watch?v=dQF0zyaym8A

Read More

Segment trees VS Interval trees VS binary indexed trees VS range trees

All these data structures are used for solving different problems:

• Segment tree stores intervals, and optimized for "which of these intervals contains a given point" queries.
• Interval tree stores intervals as well, but optimized for "which of these intervals overlap with a given interval" queries. It can also be used for point queries - similar to segment tree.
• Range tree stores points, and optimized for "which points fall within a given interval" queries.
• Binary indexed tree stores items-count per index, and optimized for "how many items are there between index m and n" queries.

Performance / Space consumption for one dimension:

• Segment tree - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space
• Interval tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
• Range tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
• Binary Indexed tree - O(n logn) preprocessing time, O(logn) query time, O(n) space

(k is the number of reported results).
All data structures can be dynamic, in the sense that the usage scenario includes both data changes and queries:

• Segment tree - interval can be added/deleted in O(logn) time (see here)
• Interval tree - interval can be added/deleted in O(logn) time
• Range tree - new points can be added/deleted in O(logn) time (see here)
• Binary Indexed tree - the items-count per index can be increased in O(logn) time

Higher dimensions (d>1):

• Segment tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1)) space
• Interval tree - O(n logn) preprocessing time, O(k+(logn)^d) query time, O(n logn) space
• Range tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space
• Binary Indexed tree - O(n(logn)^d) preprocessing time, O((logn)^d) query time, O(n(logn)^d) space

Reference 
http://stackoverflow.com/questions/17466218/what-are-the-differences-between-segment-trees-interval-trees-binary-indexed-t

Read More

Merge Overlapping Intervals

Problem

Given a collection of intervals, merge all overlapping intervals.

Input - Collection of intervals
Output - Collection of mutually exclusive intervals after merging

Example

Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution

Method 1 - Brute force
A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval. Repeat the same steps for remaining intervals after first. This approach cannot be implemented in better than O(n^2) time.

Method 2 -  Sort on the basis of start time and merge

An efficient approach is to first sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].
Following is the detailed step by step algorithm :

1. Sort the intervals based on increasing order of starting time.
2. Select the first element from the collection of intervals. Lets call it A
3. For each interval in the collection do the following
   1. If the current interval does not overlap with the A,do nothing.
   2. If the current interval overlaps with A and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval. Put it in new list called result
4. At the end result collection will contain the merged intervals.

Code in java
In java, we can sort any object provided we write implement the comparator interface. Then we can simply use Collections. sort() utility. You can sort the intervals in other languages, in some other way. So, lets stay language agnostic. I just wanted to update you that.

class Interval {
 int start;
 int end;
 
 Interval() {
  start = 0;
  end = 0;
 }
 
 Interval(int s, int e) {
  start = s;
  end = e;
 }
}

class IntervalComparator implements Comparator<Interval> {
 public int compare(Interval i1, Interval i2) {
  return i1.start - i2.start;
 }
}
 
public class Solution {
 public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
 
  if (intervals == null || intervals.size() <= 1)
   return intervals;
 
  // sort intervals by using self-defined Comparator
  Collections.sort(intervals, new IntervalComparator());
 
  ArrayList<Interval> result = new ArrayList<Interval>();
 
  Interval prev = intervals.get(0);
  for (int i = 1; i < intervals.size(); i++) {
   Interval curr = intervals.get(i);
 
   if (prev.end >= curr.start) {
    // merged case
    Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
    prev = merged;
   } else {
    result.add(prev);
    prev = curr;
   }
  }
 
  result.add(prev);
 
  return result;
 }
}

Time complexity - O(n log n) + O(n) = O(n log n)

Read More

Find the time period with the maximum number of overlapping intervals

Problem

There is one very famous problem. I am asking the same here. There is number of elephants time span given, here time span means, year of birth to year of death. You have to calculate the period where maximum number of elephants are alive.

Example :

 1990 - 2013
 1995 - 2000
 2010 - 2020
 1992 - 1999

Answer is   1995 - 1999

Solution

Pseudocode

• Split each date range into start date and end date.
• Sort the dates. If a start date and an end date are the same, put the end date first (otherwise you could get an empty date range as the best).
• Start with a count of 0.
• Iterate through the dates using a sweep-line algorithm:
  
  • If you get a start date:
    
    • Increment the count.
    • If the current count is higher than the last best count, set the count, store this start date and set a flag.
  • If you get an end date:
    
    • If the flag is set, store the stored start date and this end date with the count as the best interval so far.
    • Reset the flag.
    • Decrement the count.

Example:
For input:

1990 - 2013
1995 - 2000
2010 - 2020
1992 - 1999

Split and sorted: (S = start, E = end)

1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E

Iterating through them:

count = 0
lastStart = N/A
1990: count = 1
      count = 1 > 0, so set flag
        and lastStart = 1990

1992: count = 2
      count = 2 > 0, so set flag
        and lastStart = 1992

1995: count = 3
      count = 3 > 0, so set flag
        and lastStart = 1995

1999: flag is set, so
        record [lastStart (= 1995), 1999] with a count of 3
      reset flag
      count = 2

2000: flag is not set
      reset flag
      count = 1

2010: count = 2
      since count = 2 < 3, don't set flag

2013: flag is not set
      reset flag
      count = 1

2020: flag is not set
      reset flag
      count = 0

What if the number of elephants are very large?
For a (very) large number of elephants, it might be worth skipping the sort. You could create an array indexed by year with +1 for birth, -1 for death. O(e) to fill, and O(n) to sweep, where e is number of elephants and n is date range.


Reference

• http://stackoverflow.com/questions/19155454/find-the-time-period-with-the-maximum-number-of-overlapping-intervals

Read More