## 2.3.2 EL PROBLEMA DE SELECCIÓN DE ACTIVIDADES

Tenemos que elegir de entre un conjunto de actividades:

- Para cada actividad, conocemos su hora de comienzo y su hora de finalización.
- Podemos asistir a todas las actividades que queramos.
- Sin embargo, hay actividades que se solapan en el tiempo y no podemos estar en dos sitios a la vez.

Posibles objetivos:

> 1. Asistir al mayor número de actividades posible.

> 2. Minimizar el tiempo que estamos ociosos.

Problema de selección de actividades

Dado un conjunto C de n actividades, con:

- si = tiempo de comienzo de la actividad i.
- fi = tiempo de finalización de la actividad i.

Encontrar el subconjunto S de actividades compatibles de tamaño máximo (esto es, actividades que no se solapen en el tiempo).

Elementos del problema

- Conjunto de candidatos: C = {actividades ofertadas}.
- Solución parcial: S (inicialmente, S=Ø).
- Función de selección: menor duración, menor solapamiento, terminación más temprana.
- Función de factibilidad: x es factible si es compatible (esto es, no se solapa) con las actividades de S.
- Criterio que define lo que es una solución: C=Ø.
- Función objetivo (lo que tratamos de optimizar): El tamaño de S.

Estrategias

Estrategias ávidas (greedy) alternativas.

Orden en el que se pueden considerar las actividades:

- Orden creciente de hora de comienzo.
- Orden creciente de hora de finalización.
- Orden creciente de duración: fi - si.
- Orden creciente de conflictos con otras actividades (con cuántas actividades se solapa).

###