I'm trying to divide a list of intervals into non-overlapping subintervals. For example, if my input were
[1,5],[4,9],[6,12],[11,17]
I would want the output to be
[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]
I want the output to be a list of intervals that has the same union as the original list of intervals but where every overlapping sub-interval of multiple different subintervals is made into a different interval.
My first thought is that I should sort all intervals by their first element, and if there is an overlap I should create a new interval, but I've been having some trouble getting this to work. This seems different in nature than many interval problems, so any suggestion would be great!
Sort your original interval end-points. Then every consecutive pair of end-points defines an interval in your output unless the interval is not contained in the union of your original intervals. To determine whether an interval is contained in the union of your original intervals, process end-points from left to right and maintain a count of how many original intervals are currently overlapping the interval between the two endpoints. When you encounter a left-end point of an original interval, you increase the count by 1 and when you encounter a right-end point of an original interval, you decrease the count by 1. If the count is greater than 0 then the current interval between the two end points should be included in your output, otherwise not.