How to converge n windows(of start and end indices) to the least possible no. of windows such that all indices are covered

Issue

This Content is from Stack Overflow. Question asked by newbie101

I define a window here as a tuple which has 2 items – the start and end (respectively) indices of an object. So the tuple (0,3) means that the window (0,3) has start_index = 0 and end_index=3

Sample list of 6 windows

[(0,1) , (0,3) , (4,9) , (5,9), (6,8) , (11,13)]

Desired output:

[(0, 3), (4, 9), (11, 13)]

As you can see , in the output the no. of windows have been reduced to 3 compared to 6 windows in the input — and no index in the middle of any window is “lost”.

I have given it a shot myself but am not finding the desired results as my output contains more no. of windows than desired and I have to feed that output again in my “script” to get to the final stage.. It’s basically converging windows wherever possible (when overlaps btw windows happen in terms of the indices in the window)

Here’s my code:

list_ = [(0,1) , (0,3) , (4,9) , (5,9), (6,8) , (11,13)]

#creating a copy of list_ as I need to remove items when I iterate..
list_copy = list(list_)

new_list = []

for i in list_:
    for j in list_:
        if i != j:
            if (i[0] >= j[0]) and (i[1] <= j[1]):
                
                new_list.append(j)
                
                if i in list_copy:
                    list_copy.remove(i)
                if j in list_copy:                    
                    list_copy.remove(j)

output  = list(set(new_list + list_copy))

print("list_copy:",list_copy)
print("new_list:",new_list)    
print("output:",output)

Results for my code are as below , which has the window (5,9) unnecessarily. It gets removed if I rerun my piece of code for the output I have received from the 1st run.

list_copy: [(11, 13)]
new_list: [(0, 3), (4, 9), (4, 9), (5, 9)]
output: [(5, 9), (0, 3), (4, 9), (11, 13)]



Solution

Check the Answers

This Question and Answer are collected from stackoverflow and tested by JTuto community, is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?