hello people good afternoon
There will be a mathematical theorem that allows solving the problem k: "surveillance" of icpc 2014. I need tips on how to better deal with the problem and since there is to take it to a java environment, for the moment I need your advice to what kind of theories would be necessary for address the subject of "surveillance" I hope you do not get upset please, thank you ...
below a little of what I have with arrayList:
import java.util.ArrayList;
public class Integers {
private ArrayList<Integer> numbers;
public Integers(int a, int b, int limit) {//constructor
this.numbers = new ArrayList<Integer>();
makeList(a, b, limit);
}
public void makeList(int a, int b, int limit) {
if (a < b) {
while (a <= b) {
this.numbers.add(a);
a++;
}
} else {
int aux = 1;
while (aux <= b) {
this.numbers.add(aux);
aux++;
}
int aux2 = a;
while (aux2 <= limit) {
this.numbers.add(aux2);
aux2++;
}
}
}
public void showNumbers() {
for (int x = 0; x < this.numbers.size(); x++) {
System.out.print(this.numbers.get(x) + "\t");
}
}
}
I leave the problem statement:
Input
The input consists of a single test case. Its first line contains two integers n and k (3 ≤ n ≤ 106) and (1 ≤ k ≤ 106), where n is the number of walls and k is the number of possible places for installing cameras. Each of the remaining k lines contains two integers ai and bi (1 ≤ ai, bi ≤ n). These integers specify which walls a camera at the i
th place would cover. If ai ≤ bi
then the camera covers each wall j
such that ai ≤ j ≤ bi.
If ai > bi then the camera covers each wall j such that ai ≤ j ≤ n or 1 ≤ j ≤ bi.
Output
Display the minimal number of cameras that suffice to cover each wall of the building. The ranges
covered by two cameras may overlap. If the building cannot be covered, display impossible instead.
