I have a nested list in which I need to compare values...

Question

I have a list of lists composed of tuples representing blocks of military times:

[[(1405, 1525)],[(1405,1455),(1605,1655)],[(1505,1555),(1405,1455),(1305,1355)]]

I have a function to compare the times of two tuples:

def doesOverlap(tuple1, tuple2):
    #tuples each represent times for courses
    #the 0 index for each tuple is a start time
    #the 1 index is an end time
    A=int(tuple1[0])
    B=int(tuple1[1])
    C=int(tuple2[0])
    D=int(tuple2[1])

    if A<B and B<=C and C<=D:
        print(False, (A,B), (B,C))
    elif C<D and D<=A and A<B:
        print(False, (A,B), (B,C))
    else:
        print(True, (A,B), (B,C))

I need to compare the times from the nested list such that the first tuple in the first list compares to the first tuple of the second using doesOverlap. If the function returns True, the first tuple of the first list should be compared to the second tuple of the second list, and so on. If the function returns False, I need to compare the first tuple from the third list to the tuples that returned False.

I'm having trouble figuring how to call the function in that order. Any suggestions?

EDIT: Here's the exact homework problem:

This method is the first of the two greedy scheduling algorithms you will write. With this particular algorithm, you will look through your list of classes and schedule them in order from the class with the least amount of possible meeting times to the class with the most number of possible meeting times. When you find the course (which you haven’t already scheduled) with the least number of listed meeting times, start at the beginning of the list of times for that course and check each value sequentially until you find one which does not conflict with courses you have already scheduled. When you find this time, add it to the schedule and move onto the course with the next lowest number of meeting times. Continue this process until you have attempted to add a time for every course. Once you are finished, return the resulting list which contains the schedule. Note that you should not modify the Dictionary which contains all of your courses and meeting times during the course of running this method.

I need to call doesOverlap from a separate function, the function described above.

Answer 1

I think you are probably being too specific in your question; if you give more details about the problem, we can probably find a better solution that avoids this slightly icky iteration.

That said, I don't think your problem as stated makes sense. If I have understood it correctly, you have three lists (L1, L2, L3 say). You are only interested in the first tuple of L1, so call that initial. Then you want to compare initial to each of the tuples of L2, recording which of them return False. Finally, you want to compare the first tuple of the L3 to the recorded tuples?

I think that's probably not what you meant, because you haven't stated the iteration protocol very clearly. Still, on the off-chance that it actually was, here's some code.

([initial, *_], L2, [final, *_]) = [<redacted>]
[doesOverlap(final, b) for b in (a for a in L2 if not doesOverlap(initial, a))]

EDIT

Well, I don't really want to do your homework for you, but here's my main piece of advice first: write the algorithm in English before you start to implement it. You are getting bogged down in messy details that you don't need to worry about.

Right, code. You first need to sort the list of classes by number of meeting times. Then;

For each class in the list of classes:

For each possible time of the class can be:

If that time overlaps:

Skip it.

If not, add it to the schedule and skip the rest of the times.

Answer 2

Did try to understand the problem and try something.

It only prints if there is an overlap of time with successive data points. Also I added assert to ensure that end is always greater than start, else data is erroneous. Made it verbose to just illustrate it well.

dataPoints = [[(1405, 1525)],[(1405,1455),(1605,1655)],[(1505,1555),(1405,1455),(1305,1355)]]
# dataPoints[0] # First list
# dataPoints[1] # Second list

def doesOverlap(input_time, compare_list):
    for time_el in input_time:
        start, end = time_el[0], time_el[1]
        # assert that end is greater than start
        assert end > start
        for compare_time_data in compare_list:
            # assert that end is greater than start
            start_to_compare, end_to_compare = compare_time_data[0], compare_time_data[1] 
            assert end_to_compare > start_to_compare
            # After sanitation compare for overlap
            # Logic: Overlap can only occur if start time less than the end time if we are not woried about AM, PM and Dates
            if start_to_compare < end:
                print 'True',  time_el, compare_time_data
            else:
                print 'False',  time_el, compare_time_data


doesOverlap(dataPoints[0], dataPoints[1])

Output:

True (1405, 1525) (1405, 1455)
False (1405, 1525) (1605, 1655)

Answer 3

I do not understand your comparisions, so I made code which checks the ordering of times and after order of times is established, sees if the time periods overlap by comparing finishing time of first to start time of second. In that case my function returns True, value (instead of just printing out) of periods combined and the overlap time period, in other case my function returns False and the times in corrected order of occuring and beginning time first. I do not know if this is something you want to do. But that is my logic which you can code like I did. Here is sample of my programs output:

Given start: (1300, 1345) Given end: (1525, 1345)

Separate periods (1300, 1345) and (1345, 1525)

---

Given start: (1405, 1455) Given end: (1545, 1454)

Combined period (1405, 1545), overlap (1454, 1455)

---

Given start: (1305, 1405) Given end: (1403, 1455)

Combined period (1305, 1455), overlap (1403, 1405)

Given start: (1305, 1455) Given end: (1505, 1555)

Separate periods (1305, 1455) and (1505, 1555)

---