daily log 10.04.20

CHALLENGE

Given a list of intervals, remove all intervals that are covered by another interval in the list.

Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.

After doing so, return the number of remaining intervals.

QUESTIONS TO MYSELF:

Would I be helped by a dictionary? I don’t think so

Passes Initial Test

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """

        curr_intervals = intervals

        def check_remaining_intervals(lower, upper, i):
            for ii,curr_interval in enumerate(curr_intervals):
                curr_lower = curr_interval[0]
                curr_upper = curr_interval[1]

                if (curr_lower < lower) and (curr_upper > upper):
                    curr_intervals.pop(i)
                    print('ci 1', curr_intervals)

                # if (curr_lower > lower) and (curr_upper < upper):
                #     curr_intervals.pop(ii)
                #     print('ci 2', curr_intervals)

        for i,interval in enumerate(intervals):
            lower = interval[0]
            upper = interval[1]
            check_remaining_intervals(lower, upper, i)

        return len(curr_intervals)

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """

        curr_intervals = intervals

        def check_remaining_intervals(lower, upper, i):
            for ii,curr_interval in enumerate(curr_intervals):
                curr_lower = curr_interval[0]
                curr_upper = curr_interval[1]

                # if (curr_lower <= lower) and (curr_upper >= upper):
                if (curr_lower >= lower) and (upper >= curr_upper):
                    curr_intervals.pop(i)
                    print('ci 1', curr_intervals)

                # if (lower <= curr_lower) and (upper >= curr_upper):
                #     curr_intervals.pop(ii)
                #     print('ci 2', curr_intervals)

        for i,interval in enumerate(intervals):
            lower = interval[0]
            upper = interval[1]
            check_remaining_intervals(lower, upper, i)

        return len(curr_intervals)

Before Refactor

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """

        curr_intervals = intervals

        def check_remaining_intervals(lower, upper, i):
            for ii,curr_interval in enumerate(curr_intervals):
                curr_lower = curr_interval[0]
                curr_upper = curr_interval[1]

                # if (curr_lower < lower) and (curr_upper > upper):
                if i != ii:
                    if (curr_lower <= lower) and (upper <= curr_upper):
                        curr_intervals.pop(i)
                        print('ci 1', curr_intervals)

                    if (curr_lower >= lower) and (upper >= curr_upper):
                        curr_intervals.pop(ii)
                        print('ci 2', curr_intervals)

        for i,interval in enumerate(intervals):
            lower = interval[0]
            upper = interval[1]
            check_remaining_intervals(lower, upper, i)

        return len(curr_intervals)

Before second refactor

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """

        curr_intervals = intervals

        def check_remaining_intervals(lower, upper, i):
            for ii,curr_interval in enumerate(curr_intervals):
                curr_lower = curr_interval[0]
                curr_upper = curr_interval[1]


                if i != ii:
                    if (lower >= curr_lower) and (upper <= curr_upper):
                        curr_intervals.pop(i)

                    if (lower <= curr_lower) and (upper >= curr_upper):
                        curr_intervals.pop(ii)


        for i,interval in enumerate(intervals):
            lower = interval[0]
            upper = interval[1]
            check_remaining_intervals(lower, upper, i)

        return len(curr_intervals)

Final submission

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """

        remaining = len(intervals)

        for i, (a,b) in enumerate(intervals):
            for j, (c,d) in enumerate(intervals):
                if (i!=j) and (c<=a) and (b<=d):
                    remaining -= 1
                    break
        return remaining