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