MAC0122 Princípios de Desenvolvimento de Algoritmos (2023ii, EC/EP)

Faça o Web Exercise 4.2.1, Union of Intervals, de IntroCS,

http://introcs.cs.princeton.edu/java/42sort/

seguindo as especificações abaixo.  Seu programa deve chamar-se UnionOfIntervals.java. Seu programa deve receber os intervalos na entrada padrão, um intervalo por linha, cada intervalo dado pelo seu extremo esquerdo seguido de seu extremo direito. Por exemplo, o exemplo no enunciado do Web Exercise 4.2.1 poderia ser dado como segue:

1.0 3.0
2.0 4.5
6.0 9.0
7.0 8.0

Por simplicidade, vamos supor que os intervalos da entrada serão intervalos contidos no intervalo [0, 1]. Obviamente, para verificar se seu programa funciona com o exemplo acima, você pode fornecer a entrada

0.1 0.3
0.2 0.45
0.6 0.9
0.7 0.8

ao seu programa. Seu programa deve rodar em tempo \(O(N\log N)\), onde $N$ é o número de intervalos na entrada. Para experimentar seu programa com entradas grandes, você pode usar o programa RandomIntervals.java dado abaixo.

Seu programa deve ter dois modos de execução. No modo "verboso", ele deve listar os intervalos que constituem a união dos intervalos dados, deve dizer quantos intervalos constituem a união (como abaixo), e deve também produzir uma janela com uma figura, como no exemplo anexo (example.png). Para especificar o modo "verboso", deve bastar o usuário dar um argumento (qualquer) na linha de comando (a execução abaixo gera a imagem em example.png):

$ java-introcs UnionOfIntervals -v < example.in
Total length: 0.65 [2 components]
[0.1, 0.45]
[0.6, 0.9]
$

Eis mais um exemplo (figura: 10-.15-122.png):

$ java-introcs RandomIntervals 10 .15 122 | java-introcs UnionOfIntervals -v
Total length: 0.32259071985161547 [5 components]
[0.11690295149866328, 0.13443692535022472]
[0.37031005008801626, 0.40068715045736214]
[0.4252469689158414, 0.46795245783092976]
[0.5165433247970217, 0.5215002942607693]
[0.5805463361725651, 0.8075635234244374]
$

No modo "não verboso" (sem argumento na linha de comando), seu programa deve simplesmente dizer a soma dos comprimentos dos intervalos na união e deve dizer quantos intervalos constituem a união, como nos exemplos a seguir (seu programa não deve gerar figuras):

$ time java-introcs RandomIntervals 500000 .00001 122 | java-introcs UnionOfIntervals
Total length: 0.9182102377635738 [40934 components]

real 0m1.267s
user 0m2.402s
sys 0m0.551s
$ time java-introcs RandomIntervals 1000000 .00001 122 | java-introcs UnionOfIntervals
Total length: 0.9932559713867744 [6783 components]

real 0m2.392s
user 0m4.058s
sys 0m1.106s
$ time java-introcs RandomIntervals 2000000 .00001 122 | java-introcs UnionOfIntervals
Total length: 0.9999512330291814 [93 components]

real 0m4.507s
user 0m6.586s
sys 0m2.057s
$ time java-introcs RandomIntervals 4000000 .00001 122 | java-introcs UnionOfIntervals
Total length: 0.9999976660965318 [1 component]

real 0m8.945s
user 0m13.546s
sys 0m4.122s
$

Observação. Você pode supor que seu programa será executado no modo verboso somente para uma quantidade não muito grande de intervalos; digamos, no máximo 40 intervalos.

Importante.  Use, obrigatoriamente, a classe Interval1D.java para implementar seu programa. Veja

http://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/Interval1D.html

Não será necessário você estudar a implementação de Interval1D.java, mas não deixe de estudar o unit test de Interval1D.java:

https://algs4.cs.princeton.edu/12oop/Interval1D.java.html

Comparators.  Você pode ler sobre comparators em

http://algs4.cs.princeton.edu/25applications/

Comparators são também discutidos nas páginas de 38 a 48 de

https://algs4.cs.princeton.edu/lectures/keynote/22Mergesort.pdf

(veja a página 45).  Veja também

https://www.ime.usp.br/~yoshi/2023ii/mac0122/sandbox/2023.11.01/COMPARATORS/

Rotina de ordenação.  Use a rotina sort() de Arrays.java em seu programa.

Tempo de execução.  Seu programa deve apresentar tempos de execução grosso modo comparáveis com os tempos nos exemplos acima e no arquivo experiments.txt.

Entrega.  Entregue apenas seu programa UnionOfIntervals.java.

Observação (19/11/2023).  Arquivo example_runs.txt anexado.  Veja esta mensagem.