Actually the algorithm you are proposing is indeed linear. Here is another one, a bit more complicated, but faster:
- You need to use a Cumulative Table data structure, like Binary Indexed Tree (BIT). A BIT allows you to implement the following operations with logarithmic complexity:
- Update lo, hi, val: add at the indices [lo, hi] the value val
- Query x: return the sum at index x
- For each region [lo, hi], you call Update(lo, hi, 1), adding 1 to the appropriate positions in the BIT
- For each query just check if Query(x) is zero. If yes, then x, does not overlap with a region
About Binary Indexed Trees: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
And some code:
public class BIT {
// AddAtPosition: adds at binary indexed tree [bit] the value [v]
// exactly at position [i]. The binary indexed tree has size [size]
public static void AddAtPosition(int [] bit, int size, int i, int v) {
while(i < size) {
bit[i] += v;
i += (i & -i);
}
}
// AddAtInterval: adds at binary indexed tree [bit] the value [v]
// to all position from [lo] to [hi]. The binary indexed tree has size [size]
public static void AddAtInterval(int [] bit, int size, int lo, int hi, int v) {
AddAtPosition(bit, size, lo+1, v);
AddAtPosition(bit, size, hi+2, -v);
}
// QueryAtPosition: returns the value of index [i] at binary indexed tree [bit]
public static int QueryAtPosition(int [] bit, int i) {
int ans = 0;
i++;
while(i > 0) {
ans += bit[i];
i -= (i & -i);
}
return ans;
}
public static void main(String [] args) {
int [] bit = new int[10+1]; // for values from 0-9
AddAtInterval(bit, 11, 0, 5, 1);
AddAtInterval(bit, 11, 4, 7, 1);
for(int i=0; i<=9; ++i) {
System.out.print("Query At position " + i + ": ");
System.out.println(QueryAtPosition(bit, i));
}
}
}