%\rput(-0.5,0.1){\nathanliveVidWithoutText}
La première chose à faire est de se demander sur quel(s) critère(s) nous allons réfléchir pour optimiser les locations. Pour que deux demandes de location soient possibles, il faut que les périodes ne se chevauchent pas (par exemple, $[2~;8]$ et $[7~;9]$ sont impossibles à satisfaire).

On va donc trier les périodes selon leur date de fin.

Prenons l'exemple de la demande suivante :
\begin{center}
\begin{tabular}{|L|*9{Zc|}}
\hline
Clients $i$ & 1&2&3&4&5&6&7&8&9\\
\hline
Débuts de périodes $d_i$ & 1 &2& 4& 1& 5& 8& 9& 13& 11\\
\hline
Fins de périodes $f_i$ & 8 &5 &7 &3 &9 &11& 10& 16& 14\\
\hline
\end{tabular}
\end{center}

Après avoir trié selon les dates de fins croissantes, on obtient :

\begin{center}
\begin{tabular}{|L|*9{Zc|}}
\hline
Clients $i$ & 4 &2& 3& 1& 5& 7& 6 &9& 8\\
\hline
Débuts de périodes $d_i$ & 1 &2 &4 &1 &5 &9 &8 &11& 13\\
\hline
Fins de périodes $f_i$ & 3& 5& 7 &8 &9 &10& 11 &14 &16\\
\hline
\end{tabular}
\end{center}

\Par

Ensuite, on satisfait les demandes possibles de la gauche vers la droite :

\begin{itemize}
\item la demande du client 4 est satisfaite;
\item celle du client 2 ne l'est pas car la date du début est inférieure à celle de la fin de la demande précédente;
\item celle du client 3 est satisfaite car la date du début est supérieure à celle de la demande précédente;
\item etc.
\end{itemize}
Les clients 4, 3, 7 et 9 voient alors leur demande satisfaite.

Un algorithme glouton est alors le suivant, après tri (donc sur le 2\ieme{} tableau dans l'exemple que nous avons pris):

\begin{algorithme}{}
c $\leftarrow$ liste des numéros de clients (4, 2, ..., 8
\hspace*{6.5cm}pour notre exemple)
s $\leftarrow$ liste des numéros de clients à satisfaire
s[0] $\leftarrow$ c[0] (1\ier client satisfait)
fin $\leftarrow$ f[0]
Pour i allant de 1 à n-1:
\quad Si d[i] $\geqslant$ fin:
\qquad s[k+1] $\leftarrow$ c[i]
\qquad fin $\leftarrow$ f[i]
\quad Fin du Si
Fin du Pour
\end{algorithme}

\Par

Pour chaque client, on regarde si la date de début de période est supérieure ou égale à la date de fin de la période du dernier client satisfait. Si tel est le cas, ce client est ajouté à la liste des clients satisfaits et la variable \texttt{fin} prend la valeur de la date de fin de la période du client ajouté, pour servir de référence pour les clients suivants.
