Algoritmo Selección de Actividades en C++

Este fue el tema final para la exposición de mi proyecto en Técnicas de Construcción de Programas, recopile información de muchos sitios web para lograr entender y asi poder implementar. Espero que les guste este pequeño aporte.

Suponga que se cuenta con un conjunto S ={a1, . . . , an}, de actividades que necesitan usar un recurso que no puede ser usado sino por una actividad a la vez. Cada actividad ai tiene un tiempo inicial si y final fi asociados, tal que si≤ fi< ∞.

Las actividades ai y aj son compatibles si la intersección de los intervalos [si, fi) ∩[sj, fj) = φ.

El problema de selección de actividades:
Entrada: S = {a1, ..., an} si, fi1 ≤ i ≤ n
Salida: A ⊆ S: todas las actividades de A son mutuamente compatibles, y | A | es el máximo posible.

Las actividades representadas de forma grafica :

Los subconjuntos : {a3, a9, a11}, {a1, a4, a8, a11}, {a2, a4, a9, a11} estan compuestos de actividades mutuamente compatibles.

Criterio de selección voraz

1. La parte fundamental de un algoritmo voraz es su criterio de seleccion voraz:
2. Seleccionar la actividad que comience mas temprano.
3. Seleccionar la actividad de menos duracion.
4. Seleccionar la actividad que termine m as pronto.
5. Seleccionar la actividad que menos solapamientos tenga con el resto de actividades candidatas.
6. Para que puedan formar una solucion, debemos adjuntarles el criterio de completabilidad: que no se solape con las actividades ya seleccionadas.

Algoritmo

Implementación