Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Алгоритм пересечения числовых интервалов

20K
30 октября 2011 года
Dj Flip
3 / / 11.09.2006
Есть несколько числовых интервалов. Например,

1) 0-100
2) 40-50
3) 120-180
4) 200-300
5) 800-1000
6) 299-801
7) 1001-1100
...

Необходимо вычислить какие интервалы пересекаются. Какой наиболее оптимальный алгоритм?
41K
30 октября 2011 года
kisssko
108 / / 28.10.2010
Если интервалы статические, то некоторые компиляторы (gcc, tcc, pcc, peles-c) поддерживают switch с интервалами (это по C99, ЕМНИП).
Если проект для MSVC++, то можно сделать либу, ибо последний этой фичи не поддерживает.

В противном случае же можно сделать примерно так.

Код:
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);
}


Возможны ошибки, писал наспех, не проверял.
360
31 октября 2011 года
P*t*
474 / / 15.02.2007
Отсортировать все концы отрезков и идти слева на право, храня список отрезков у которых уже было начало, но еще не было конца. Отрезки, которые в какой-то момент обновременно были в списке, пересекаются.
В двумерном случае это называется "метод сканирующей прямой".

Время работы - O(n log n) на сортировку и O(n) на проход по концам. Вариант kisssko, как мне кажется (лень вникать в код), работает медленнее.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог