Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Range in range (solution 1)
import data_structure.fenwick.FenwickTree;
import java.util.Arrays;
public class CountRangeCoveringRange {
/**
* Counts how many ranges in [l,r).
* Answers multiple query.
*
* O((n+q)log(n+q) where q = query.length, n = ranges.length
*
* @param ranges array of [l,r)
* @param query answerCountQuery query
* @return answers to the queries
*/
public static int[] answerCountQuery(int[][] ranges, int[][] query) {
int n = ranges.length;
int q = query.length;
int[][] qinfo = new int[n+q][3];
for (int i = 0; i < q ; i++) {
qinfo[i] = new int[]{ query[i][0], query[i][1], i };
}
for (int i = 0; i < n ; i++) {
qinfo[q+i] = new int[]{ ranges[i][0], ranges[i][1], -1 };
}
Arrays.sort(qinfo, (a, b) -> (a[1] == b[1]) ? a[2] - b[2] : a[1] - b[1]);
// it may need value compression.
FenwickTree bit = new FenwickTree(1000010);
int[] ans = new int[q];
int head = 0;
for (int i = 0; i < n+q ; i++) {
if (qinfo[i][2] == -1) {
// target range
bit.add(qinfo[i][0]+1, 1);
} else {
// query range
ans[qinfo[i][2]] = (int)bit.range(qinfo[i][0]+1, qinfo[i][1]);
}
}
return ans;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment