I два набора интервалов, которые соответствуют одному и тому же одномерному (линейному) пространству. Вот грубое визуальное представление - на самом деле интервалов намного больше, и они гораздо более разбросаны, но это дает основную идею.
Каждый из этих интервалов содержит информацию, и я пишу программу для сравнения информации в одном наборе интервалов (красный) с информацией, содержащейся в другом наборе (синий).
Вот моя проблема. Я хотел бы разделить пространство на n чанков так, чтобы в каждом чанке выполнялось примерно одинаковое количество операций сравнения (объем работы зависит от количества интервалов в этой части пространства ). Кроме того, раздел не должен разбивать любой красный или синий интервал между двумя фрагментами.
Таким образом, входное значение представляет собой два набора интервалов, а желаемое выходное значение представляет собой раздел пространства, такой что
- интервалы (примерно) равномерно распределены по каждому элементу раздела
- нет интервалов перекрытия с несколькими элементами разбиения
Кто-нибудь может предложить подход или алгоритм для этого?