Leiam o enunciado do problema.
Este é um exemplo direto de um problema designado por interval coverage. Dado um intervalo inicial [A,B] e um conjunto de intervalos [L_i, R_i], encontrar o número mínimo destes que cubram a totalidade do intervalo inicial.
Este problema clássico tem uma solução greedy que é possível de reutilizar noutros locais dado ser um tema que aparece em vários problemas de programação competitiva.
Para tal precisamos primeiro ordenar os intervalos da seguinte forma: primeiro ordenados de forma crescente pelos valores L_i, e nos seus valores iguais, ordenados de forma decrescente pelos R_i. Por exemplo, [0,2] < [0,1] < [1,2].
Na nossa solução vamos representar estes intervalos [L_i, R_i] como objectos da classe privada Pair
public class UVa_10020_MinimalCoverage {
private static class Pair implements Comparable<Pair>{
int l, r;
Pair(int l, int r) {
this.l=l; this.r=r;
}
public String toString(){
return "[" + l + "," + r + "]";
}
// eg: [0,2] < [0,1] < [1,2]
@Override
public int compareTo(Pair p2) {
if (this.l>p2.l) return 1;
if (this.l<p2.l) return -1;
return this.r<p2.r ? 1 : -1;
}
}
...
No nosso problema actual, o intervalo [A,B] tem o formato [0,M]. Logo, neste caso, temos de primeiro começar por um intervalo que comece antes ou no valor zero (se não houver intervalos nestas condições -- todos os intervalos são negativos -- não vamos ter solução).
A ideia é ir guardando o melhor intervalo que nos aparece correntemente, e que satisfaça ter o valor L_i à esquerda do valor desejado. Quando nos aparece um intervalo cujo valor R_i é maior, guardamos esse, dado que ainda é melhor que os intervalos encontrados até agora. Por exemplo, se temos o intervalo [-1,4] e aparece o [0,5], preferimos guardar este último dado que só precisamos cobrir o intervalo inicial a partir do zero.
Quando aparece um intervalo com um L_i que passa o valor desejado à esquerda, temos de guardar o melhor que encontramos até agora. Continuando o exemplo: se depois do [0,5] nos aparece um [2,7], temos de guardar o [0,5] dado que mais nenhum intervalo vai aparecer que cubra o 0 (lembrem-se que ordenámos os intervalos).
O novo intervalo pode ser interessante ou não. No caso do [2,7] ficamos com ele (até ver). Mas se nos aparecesse o [2,4], esse não nos interessava pois esses valores já estão incluídos no [0,5] que acabámos de guardar.
Vamos repetindo isto até que o último intervalo guardado tenha um R_i maior que M, ou que ocorra uma situação onde um dos valores que procuramos à esquerda ou à direita não possa ser satisfeito. Nesse segundo caso temos de informar que a instância do problema não tem solução.
Segue uma possível solução que utiliza este algoritmo (com bastantes comentários).
Como neste caso, cada instância do problema pode ter até 100 mil intervalos, não usamos o Scanner dado ser muito lento para ler muito input (cf. a página 'Quando é necessário ler muito input' onde está descrita a classe Reader usada a seguir).
public static void main(String[] args) {
if (!new Object(){}.getClass().getName().contains("Main"))
try { // redirect System.in and System.out to in/out text files
System.setIn (new FileInputStream("data/uva10020.in.txt" ));
System.setOut(new PrintStream("data/uva10020.out.txt") );
} catch (Exception e) {}
///////////////////////////////////////////////////////////////
try {
Reader.init( System.in );
int nCases = Reader.nextInt();
while (nCases-- > 0) {
int M = Reader.nextInt(); // defining coverage interval [0,M]
List<Pair> available = new LinkedList<Pair>(); // list of available intervals
List<Pair> coverage = new LinkedList<Pair>(); // list of minimal coverage intervals
int l, r; // read & keep pairs of available intervals until a 0 0 appears
do {
l = Reader.nextInt();
r = Reader.nextInt();
if (l != 0 || r != 0)
available.add(new Pair(l, r));
} while (l != 0 || r != 0);
available.sort((p1, p2) -> p1.compareTo(p2)); // sort pairs for greedy algorithm
// greedy algorithm
int need_left = 0; // from where we still need to cover
Pair current_best = new Pair(0, 0); // our best interval so far
boolean have_current_best = false; // have we a good interval?
boolean not_feasible = false; // is it unfeasible to cover [0,M]?
for (Pair p : available) {
if (p.l <= need_left) { // if p has good left value
if (p.r > current_best.r) { // and better right value that what we found so far
current_best = p; // let's keep it
have_current_best = true; // & flag it!
}
} else {
if (have_current_best) {
// we want to keep this one, nothing after this is going to be better
// (due to the previous pair ordering)
coverage.add(current_best);
// update requirements
need_left = current_best.r; // we need to start looking from the current best right
have_current_best = false; // and we'll restart looking for good candidates
// ...unless
if (need_left >= M)
break; // then, it's job done!
}
// since we are looking for updated values, we need to recheck the current pair
if (p.l <= need_left) {
if (p.r > current_best.l) {
current_best = p; // let's keep it
have_current_best = true;
}
} else {
// if the current's left value is higher that what we need, then we will
// not be able to satisfy the coverage, and must announce failure!
not_feasible = true;
break;
}
}
} // for
if (have_current_best) {
coverage.add(current_best);
if (current_best.r < M) // it might not be enough
not_feasible = true;
}
if (not_feasible) {
System.out.println(0 + "\n");
} else {
System.out.println(coverage.size());
for(Pair p : coverage)
System.out.println(p.l + " " + p.r);
if (nCases>0) // give extra newline except for the last case
System.out.println();
}
} // while
} catch (Exception e) {};
}
}
Outros problemas UVa resolúveis via interval converage: