Tarea 9 de Análisis y Diseño de Algoritmos
Trimestre 2014 Invierno
Entrega: 14 de marzo de 2014 a las 22:00.
Esta tarea consiste en una implementación del algoritmo glotón visto
en clase para el problema de programación de intervalos. La entrada
consiste de un entero N (con 1 <= N <= 1,000,000) seguido de N
parejas S(I), T(I) (con 0 <= S(I) < T(I) <= 1,000,000) que
corresponden con el tiempo de inicio y el tiempo de fin de la
actividad I (con 1 <= I <= N). La salida consiste de un entero
M seguido de M enteros A(1), ..., A(M) correspondientes al orden de
las M actividades que se llevarán a cabo. Escribe un programa
llamado intervalosZZ
(donde ZZ es la clave
de dos dígitos asignada por el profesor) que lleve a cabo esta
tarea.
En el ejemplo mostrado abajo hay 9 tareas. Aplicando el algoritmo
glotón se obtiene que M = 4 y que las tareas que se deben ejecutar
son la 3, 4, 5 y 2 en ese orden.
Ejemplo de entrada
|
Ejemplo de salida
|
9
1 18
19 24
0 3
4 9
10 15
17 27
2 6
8 12
13 21
|
4
3 4 5 2
|
Notas: Sus programas no deben leer ni escribir nada
adicional a lo que se indica en el enunciado. El tiempo
de ejecución de sus algoritmos será considerado como parte de la
evaluación.