Оптимизация задач merge_intervals (используется bfs) - PullRequest
Новая
       23

Оптимизация задач merge_intervals (используется bfs)

1 голос
/ 28 июня 2019

Я работаю над проблемой слияния перекрывающихся интервалов: Проблема Ссылка: https://www.geeksforgeeks.org/merging-intervals/

Я пытался реализовать bfs для этой проблемы, потому что ..... почему бы и нет?

Решение, которое я обнаружил, работает просто отлично. Проблема возникает, когда набор данных очень большой. Это становится относительно медленным по сравнению с другими методами для решения этой проблемы. Я хочу максимально оптимизировать этот код, чтобы он не был таким медленным.

Я попробовал словарь для поиска, установите для поиска, чтобы проверить, посещен узел или нет. Тем не менее, решение не показывает значительных улучшений. Пожалуйста, предложите мне, как я могу сделать это быстро. Я думаю, что в настоящее время он работает в O (nlogn) + O (n) 

def merge_graph(intervals,visited,i):
    #print ("-----")
    q=deque()
    q.append((intervals[i][0],intervals[i][1]))
    visited.add(i)
    temp_result=[]
    #temp_result.append(intervals[i][0])
    start_lim=sys.maxsize
    end_lim=-sys.maxsize
    while q:
        #print (q)
        left,right=q.popleft()
        start_lim=min(start_lim,left)
        end_lim=max(end_lim,right)
        for j in range(len(intervals)):
            if j not in visited and right>=intervals[j][0] and left<=intervals[j][1]:
                visited.add(j)
                q.append((intervals[j][0],intervals[j][1]))
    temp_result.append(start_lim)
    temp_result.append(end_lim)
    return (temp_result)
n=len(intervals)
visited=[0]*(n+1)
#uncomment this line for result is sorted order
#intervals.sort()
merged_intervals=[]
visited=set()
for i in range(n):
    if i not in visited:
        merged_intervals.append(merge_graph(intervals,visited,i))
return (merged_intervals)
...