Input: A set S $=\{($li

$,$ ri$)|1<=$ i $<=$ n$\}$ of n intervals denoted by their left$-$ and right$-$point

over a real line L $=(1,$ M$).$

Objective: Using the fewest number of colors, assign a color to each interval such that no

two overlapping intervals can receive the same color. $($Note that two intervals i and j when

li $<$ ri $=$ lj $<$ rj are not considered overlapped.$)$

$1$

$($a$)$ Consider the following iterative greedy algorithm. Assign color $1$ to as many intervals as

possible, then assign color $2$ to as many intervals as possible, then assign color $3$ to as many

intervals as possible, etc. Does this algorithm solve the problem? Justify your answer.

$($b$)$ Now, consider the following greedy algorithm. Process the intervals in non$-$decreasing order of

their left points, i$.$e$.,$ l$1<=$ l$2<=<=$ ln$.$ Consider intervals in this order and assign colors such

that $($i$)$ interval $1$ is assigned color $1,($ii$)$ when considering interval i$,$ if there is an interval j

such that j $<$ i and the color assigned to j can be assigned to i$,$ then assign that color to i$,$

and $($iii$)$ otherwise, assign a new color to interval i$.$ Does this algorithm solve the problem?

Justify your answer.