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 - **sorted** **Use Me**.

**Note:**

a) [1,3] represents an interval that includes 1, 2 and 3.

b) Intervals should be sorted based on the value of

**Examples: **

Input: [ [1,3], [2,5] ], Output: [ [1,5] ]

Input: [ [3,5], [1,2] ], Output: [ [1,2], [3,5] ]

`mergeIntervals`

that takes in an `ArrayList`

of integer `Interval`

s (aka ranges), and returns an `ArrayList`

of `Interval`

s where all overlapping intervals have been merged. The `Interval`

class is available by clicking a) [1,3] represents an interval that includes 1, 2 and 3.

b) Intervals should be sorted based on the value of

`start`

Input: [ [1,3], [2,5] ], Output: [ [1,5] ]

Input: [ [3,5], [1,2] ], Output: [ [1,2], [3,5] ]

Need a **hand?** Try out these hints, one at a time.

This problem becomes fairly simple to solve once you **sort** the

`ArrayList`

of `Interval`

s based on their `start`

values. To do so, use `Collections.sort`

and pass in a custom `Comparator`

that returns `Integer.compare(o1.start, o2.start)`

in its `compare`

method.
After sorting the input list of Intervals, iterate once across the list and merge overlapping intervals.

1) Initialize an output

2) Sort the input ArrayList with a custom comparator like so :

3) Create an

4) Iterate over the input list, starting at index i = 1.

5) If there is an overlap of the current interval (

6) Otherwise, add

7) As soon as the loop ends, remember to add the last remaining

`ArrayList`

2) Sort the input ArrayList with a custom comparator like so :

Collections.sort(intervalsList, new Comparator() {

public int compare(Interval o1, Interval o2) {

return Integer.compare(o1.start, o2.start);

}

});

3) Create an

`Interval`

`prev`

and set it to the first Interval in the input list.4) Iterate over the input list, starting at index i = 1.

`Interval cur = intervalsList.get(i);`

5) If there is an overlap of the current interval (

`cur.start <= prev.end`

), set `prev`

to a new `Interval`

that begins at `prev.start`

and ends at `Math.max(cur.end, prev.end)`

6) Otherwise, add

`prev`

to the output list and set `prev`

= `cur`

7) As soon as the loop ends, remember to add the last remaining

`prev`

to the list : `out.add(prev)`

public static ArrayList<Interval> mergeIntervals(ArrayList<Interval> intervalsList) { }

**C**

**Java**

**Python**