Сделать сегменты попарно непересекающимися слева.

Question

Я снабжен M сегментами [L, R] из N элементов массива. Мне нужно изменить эти сегменты таким образом, чтобы все сегменты имели попарно различные левые концы.

Пример: предположим, что у нас есть 5 элементов в массиве, и у нас есть 4 сегмента: [1,2], [1,3], [2,4] и [4,5], после чего все левые концы попарно не пересекаются, мы имеем [1,2], [3,3], [2,4] и [4,5]. Все сегменты имеют разные левые концы.

Основной вопрос состоит в том, чтобы все пары попарно не пересекались с левый конец. Если они являются двумя перекрывающимися парами, скажите [1,3] и [1,4], то измените их на [1,3] и [4,4]. Какой лучший подход к его обработке?

Answer 1

Это жадное решение, очерченное ниже. Во-первых, сортируйте сегменты на основе их левого конца и разорвите связи на основе их правых концов. Теперь перейдем через массив сегментов. Если левый конец текущего сегмента совпадает с предыдущим, просто увеличьте текущий сегмент на 1. Если левый конец текущего сегмента меньше предыдущего, сделайте левый конец текущего сегмента = left_end_of_previous_segment+1. В противном случае оставьте левый конец как есть. Теперь, если мы изменим левый конец любого сегмента, убедитесь, что правый конец не меньше, чем левый конец. Этот алгоритм принимает время O (NlgN + N)

Кстати, Если вы можете изменить любые конечные точки, и нет никаких условий для перемещения, вы можете легко сделать этот трюк. Просто запустите цикл и сделать все левые концы и правый концы = я + 1

for(int i = 0; i < N; i++) { 
    left[i] = i+1; 
    right[i] = i+1; 
} 

Приведенный выше код обеспечивает все левый конец будет различимы, но я думаю, что есть некоторые другие условия, вы пропустили, наверное? Например, вам не разрешено двигаться вправо?