interval

**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. [Read More]

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. [Read More]

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. [Read More]

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. [Read More]