Problema D - Auxílio Informático

A Cláudia é uma das principais organizadoras das Olimpíadas Nacionais de Informática. Como parte da organização da prova de qualificação das olimpíadas, a Cláudia tem N tarefas a efetuar. Cada tarefa tem um horário que é um intervalo de tempo, ou seja, a i-ésima tarefa tem de ser desempenhada entre as a_i e as b_i horas. A Cláudia só consegue realizar uma tarefa de cada vez, por isso se duas tarefas se sobrepuserem ela só consegue fazer uma de cada vez.

Parte I

A Claúdia sabe que é possível que não consiga terminar todas as tarefas visto que pode haver sobreposições, mas ela quer efetuar o máximo número de tarefas possível. Determina o máximo número de tarefas que a Cláudia consegue desempenhar.

Exemplo

Se N = 5 e tivermos o seguinte horário de tarefas:

• a₁ = 2, b₁ = 5
• a₂ = 5, b₂ = 10
• a₃ = 5, b₃ = 6
• a₄ = 7, b₄ = 8
• a₅ = 10, b₅ = 12

Que é pode ser visualizado da seguinte forma:

A tarefa 2 sobrepõe-se às tarefas 3 e 4, mas as restantes tarefas não têm sobreposições. Por isso a Cláudia pode efetuar as tarefas 1, 3, 4 e 5, para um total de 4 tarefas. A figura seguinte ilustra esta solução:

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em dois grupos:

Parte II

Para a ajudar a completar todas as tarefas, a Cláudia usou os seus conhecimentos informáticos para construir um robot que consegue efetuar qualquer uma das tarefas. Assim como a Cláudia, o robot só consegue fazer uma de cada vez.

A qualquer altura a Cláudia pode ativar o robot e quando não o quiser utilizar mais pode desligá-lo (não podendo voltar a ligá-lo novamente). Como o robot tem bateria limitada, a Cláudia quer determinar a duração do intervalo de tempo mais curto em que o robot tem de estar ligado para que ele e a Cláudia consigam terminar todas as tarefas ou determinar que não é possível os dois efetuarem todas as tarefas. Caso não seja possível efetuar todas as tarefas o output do teu programa deve ser -1.

Exemplo

Se N = 5 e tivermos o seguinte horário de tarefas:

• a₁ = 2, b₁ = 5
• a₂ = 5, b₂ = 10
• a₃ = 5, b₃ = 6
• a₄ = 7, b₄ = 8
• a₅ = 10, b₅ = 12

Que é pode ser visualizado da seguinte forma:

A tarefa 2 sobrepõe-se às tarefas 3 e 4, mas as restantes tarefas não têm sobreposições. Por isso a Cláudia pode efetuar as tarefas 1, 2 e 5 e deixar o robot efetuar as tarefas 3 e 4. Para isso o robot só precisa de estar ligado entre as 5 e as 8 horas, para um total de 3 horas. A figura seguinte ilustra esta solução:

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em dois grupos:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro N, representando o número de tarefas.

Seguem-se N linhas, cada uma contendo dois inteiros separados por espaços, a i-ésima contendo a_i e b_i, representando o intervalo de tempo para a i-ésima tarefa.

Output

Parte I

O output deve conter uma linha contendo o número máximo de tarefas que a Cláudia consegue efetuar.

Parte II

O output deve conter uma linha contendo o a duração do intervalo de tempo mais curto em que o robot tem de estar ligado para que ele e a Cláudia consigam terminar todas as tarefas ou determinar que não é possível os dois efetuarem todas as tarefas. Caso não seja possível efetuar todas as tarefas o output do teu programa deve ser -1.

Input do Exemplo 1

1
5
2 5
5 10
5 6
7 8
10 12

Output do Exemplo 1

4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo mencionado no enunciado da Parte I.

Input do Exemplo 2

2
5
2 5
5 10
5 6
7 8
10 12

Output do Exemplo 2

3

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo mencionado no enunciado da Parte II.