If you have an unsorted list of one million unique items, and know that you will only search

for an item only three times. Which algorithm would you use?

You are given a collection of intervals, where each interval is represented as a pair of integers

$[$start$,$ end$].$ The intervals may overlap with each other. Write an algorithm to merge any

overlapping intervals into a single interval.

Input: The input consists of a collection of intervals, represented as a list of pairs of integers

intervals start$1,$ end$1],[$start$2,$ end$2],...,[$startN$,$ endN$]],$ where start$\_$i and end$\_$i

denote the start and end points of the i$-$th interval, respectively.

Output: Return a new collection of non$-$overlapping intervals, where each interval is

represented similarly as a pair of integers.

Example:

Input: intervals $=\left[\begin{array}{cc}1& 3\\ 2& 6\\ 8& 10\\ 15& 18\end{array}\right]$

Output: intervals $=\left[\begin{array}{cc}1& 6\\ 8& 10\\ 15& 18\end{array}\right]$

Explanation:

The intervals $1,33$ and $2,6$ overlap, so they are merged into $1,6.$

The intervals $8,10$ and $15,18$ do not overlap with any other intervals, so they remain

unchanged.

write the code in java