int intervals[]={ /* младшие значения сортируем */
0, 100,
40, 50,
120, 180,
200, 300,
299, 801,
800, 1000,
1001, 1100
};
int *findInterval(int *arr, int cnt, int val)
{
int idx=0;
while(idx<(cnt<<1)){if(arr[idx]<=val){if(arr[idx+1]>=val){return &arr[idx];}}}
return NULL;
}
int main(int argc, char **argv)
{
int *pInterval;
if(argc<2) return 0;
pInterval=findInterval(intervals, sizeof(intervals)<<1, atoi(argv[1]));
vprintf(pInterval?"Interval: %u:%u\n":"Not found!\n", pInterval);
}
Алгоритм пересечения числовых интервалов
1) 0-100
2) 40-50
3) 120-180
4) 200-300
5) 800-1000
6) 299-801
7) 1001-1100
...
Необходимо вычислить какие интервалы пересекаются. Какой наиболее оптимальный алгоритм?
Если проект для MSVC++, то можно сделать либу, ибо последний этой фичи не поддерживает.
В противном случае же можно сделать примерно так.
Код:
Возможны ошибки, писал наспех, не проверял.
В двумерном случае это называется "метод сканирующей прямой".
Время работы - O(n log n) на сортировку и O(n) на проход по концам. Вариант kisssko, как мне кажется (лень вникать в код), работает медленнее.