Let (a; b) represent an interval (or range) of values x such that a <=x<= b . Consider an array X =<

a1,b1,a2,b2,…, an, bn > of 2n numbers representing n intervals (ai, bi) , where ai = X[2i-1] and bi =

X[2i] and ai <= bi . an algorithm called Simplify-Intervals(X) that takes an arrayX representing n

 intervals, and simplifies X in-place. The “simplification” of a set of intervals X is a minimal set of intervals

representing the union of all the intervals in X . Notice that the union of two disjoint intervals can not be

simplified, but the union of two partially overlapping intervals can be simplified into a single interval. For

example, a correct solution for the simplification ofX =< 3, 7, 1, 5, 10, 12, 6, 8 > isX =< 10, 12, 1, 8 > .

An array X can be shrunk by setting its length (effectively removing elements at the end of the array).

In this example, length(X) should be 4 after the execution of the simplification algorithm. Analyze the

complexity of Simplify-Intervals .