Suponha que você seja o coordenador de um colégio e uma de suas atribuições seja montar o horário de funcionamento das disciplinas a serem oferecidas no próximo semestre. Para tanto, você solicita aos estudantes que indiquem quais disciplinas eles pretendem cursar. Com base nestas indicações você pode tomar o cuidado de não ofertar duas disciplinas numa mesma hora se um estudante planeja cursar ambas as disciplinas.
Por outro lado, pode ser conveniente estabelecer um horário que requeira o menor número de períodos de forma a evitar aulas em horas impopulares. A questão é: qual o menor número de horas necessárias para atender às solicitações dos estudantes?