假设给你一组 N 个区间(表示为左右坐标)和 M 个点。对于每个点 P 算法应该找到 P 所属的区间数。
这是我的算法:
1)将区间的左、右坐标分别放入“left”和“right”数组中
2)“左”排序,与“右”同时交换条目
3) 给定一个点 P,找到一个最大值 i,使得 left[i]
4) 对于每个 j = P,则结果加 1
5)返回结果
Java中的实现:
import java.util.*;
class Intervals {
public static int count(int[] left, int[] right, int point) {
int k = find(left, point), result = 0;
for (int i=0; i < k; i++)
if (point <= right[i]) result++;
return result;
}
private static int find(int[] a, int point) {
if (point < a[0]) return -1;
int i = 0;
while (i < a.length && a[i] <= point) i++;
return i;
}
private static void sort(int[] a, int[] b) {
sort(a, b, 0, a.length-1);
}
private static void sort(int[] left, int[] right, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
exchange(left, right, lo, lo + (int) (Math.random() * (hi-lo+1)));
int v = left[lo];
int i = lo;
while (i <= gt) {
if (left[i] < v) exchange(left, right, lt++, i++);
else if (left[i] > v) exchange(left, right, i, gt--);
else i++;
}
sort(left, right, lo, lt-1);
sort(left, right, gt+1, hi);
}
private static void exchange(int[] left, int[] right, int i, int j) {
int temp = left[i];
left[i] = left[j];
left[j] = temp;
temp = right[i];
right[i] = right[j];
right[j] = temp;
}
private static boolean less(int[] a, int i, int j) {
return a[i] < a[j];
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int m = Integer.parseInt(args[1]);
int[] left = new int[n];
int[] right = new int[n];
Random r = new Random();
int MAX = 100000;
for (int i = 0; i < n; i++) {
left[i] = r.nextInt(MAX);
right[i] = left[i] + r.nextInt(MAX/4);
}
sort(left, right);
for (int i=0; i < m; i++)
System.out.println(count(left, right, r.nextInt(MAX)));
}
}
该代码尚未通过某些测试,我正在尝试查找错误。重点是我实际上不知道这些测试中使用了哪些输入数据。
Thanks.