A Range Module is a module that tracks ranges of numbers. Range modules are used extensively when designing scalable online game maps with millions of players. Your task is to write a method - insertRange that takes in an ArrayList of sorted, non-overlapping integerInterval s (aka ranges) and a new Interval - insert, and returns an ArrayList of sortedInterval s where insert has been added to the ArrayList in the correct spot and the required overlapping ranges have been merged. The Interval class is available by clicking Use Me. Target a time complexity of O(n).
Note: a) [1,3] represents an interval that includes 1, 2 and 3. b) Intervals should be sorted based on the value of start c) The words Range and Interval are used interchangeably
This problem simplifies things from the start by stating that the List of Intervals is already sorted, and is non-overlapping. Use this knowledge to map out 3 possible scenarios of Range insertion. They will be : a) The input range lies completely in front of the Range in consideration b) The input ranges lies completely behind the Range in consideration c) There is an overlap between the input Range and the Range in consideration