<commit_before>"""Leetcode 56. Merge Intervals
Medium

URL: https://leetcode.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
"""

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

        Time complexity: O(n^2).
        Space complexity: O(1).
        """
        if not intervals:
            return []

        # Sort by interval's start.
        intervals = sorted(intervals)

        result = [intervals[0]]

        for i in range(1, len(intervals)):
            is_merged = False
            # Iterative check all merged intervals. If updated, breack for loop.
            for j in range(len(result)):
                if (result[j][0] <= intervals[i][0] <= result[j][1] and 
                    intervals[i][1] > result[j][1]):
                    # interval's left is in merged i, but its right is not.
                    result[j][1] = intervals[i][1]
                    is_merged = True
                    break
                elif (intervals[i][0] < result[j][0] and
                      result[j][0] <= intervals[i][1] <= result[j][1]):
                    # interval's right is in merged i, but its left is not.
                    result[j][0] = intervals[i][0]
                    is_merged = True
                    break
                elif (result[j][0] <= intervals[i][0] <= result[j][1] and
                      result[j][0] <= intervals[i][1] <= result[j][1]):
                    # interval is in merged.
                    is_merged = True
                    break
                elif (intervals[i][0] < result[j][0] and
                      intervals[i][1] > result[j][1]):
                    # interval contains merged.
                    result[j] = intervals[i]
                    is_merged = True
                    break

            if not is_merged:
                result.append(intervals[i])

        return result


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

        Time complexity: O(n*logn).
        Space complexity: O(1).
        """
        if not intervals:
            return []

        # Sort by interval's start.
        intervals = sorted(intervals)

        # Iterate through intervals to append them or update end. 
        result = [intervals[0]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] > result[-1][1]:
                # If interval is not overlapped with the last, append interval.
                result.append(intervals[i])
            else:
                # If overlapped, update the result's end.
                result[-1][1] = max(intervals[i][1], result[-1][1])

        return result


def main():
    import time

    print 'By naive:'
    start_time = time.time()

    # Ans: [[1,6],[8,10],[15,18]]
    intervals = [[1,3], [2,6], [8,10], [15,18]]
    print SolutionBrute().merge(intervals)

    # Ans: [[1,5]]
    intervals = [[1,4], [4,5]]
    print SolutionBrute().merge(intervals)

    # Ans: [[0, 4]]
    intervals = [[1,4], [0,4]]
    print SolutionBrute().merge(intervals)

    # Ans: [[0,5]]
    intervals = [[1,4], [0,5]]
    print SolutionBrute().merge(intervals)

    # Ans: [[1, 10]]
    intervals = [[2,3], [4,5], [6,7], [8,9], [1,10]]
    print SolutionBrute().merge(intervals)

    print 'Time: {}'.format(time.time() - start_time)

    print 'By checking the last:'
    start_time = time.time()

    # Ans: [[1,6],[8,10],[15,18]]
    intervals = [[1,3], [2,6], [8,10], [15,18]]
    print SolutionAppendOrUpdateEnd().merge(intervals)

    # Ans: [[1,5]]
    intervals = [[1,4], [4,5]]
    print SolutionAppendOrUpdateEnd().merge(intervals)

    # Ans: [[0, 4]]
    intervals = [[1,4], [0,4]]
    print SolutionAppendOrUpdateEnd().merge(intervals)

    # Ans: [[0,5]]
    intervals = [[1,4], [0,5]]
    print SolutionAppendOrUpdateEnd().merge(intervals)

    # Ans: [[1, 10]]
    intervals = [[2,3], [4,5], [6,7], [8,9], [1,10]]
    print SolutionAppendOrUpdateEnd().merge(intervals)

    print 'Time: {}'.format(time.time() - start_time)



if __name__ == '__main__':
    main()<commit_msg>Remove redundant space line & revise class name<commit_after>"""Leetcode 56. Merge Intervals
Medium

URL: https://leetcode.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
"""

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

        Time complexity: O(n^2).
        Space complexity: O(1).
        """
        if not intervals:
            return []

        # Sort by interval's start.
        intervals = sorted(intervals)

        result = [intervals[0]]

        for i in range(1, len(intervals)):
            is_merged = False
            # Iterative check all merged intervals. If updated, breack for loop.
            for j in range(len(result)):
                if (result[j][0] <= intervals[i][0] <= result[j][1] and 
                    intervals[i][1] > result[j][1]):
                    # interval's left is in merged i, but its right is not.
                    result[j][1] = intervals[i][1]
                    is_merged = True
                    break
                elif (intervals[i][0] < result[j][0] and
                      result[j][0] <= intervals[i][1] <= result[j][1]):
                    # interval's right is in merged i, but its left is not.
                    result[j][0] = intervals[i][0]
                    is_merged = True
                    break
                elif (result[j][0] <= intervals[i][0] <= result[j][1] and
                      result[j][0] <= intervals[i][1] <= result[j][1]):
                    # interval is in merged.
                    is_merged = True
                    break
                elif (intervals[i][0] < result[j][0] and
                      intervals[i][1] > result[j][1]):
                    # interval contains merged.
                    result[j] = intervals[i]
                    is_merged = True
                    break

            if not is_merged:
                result.append(intervals[i])

        return result


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

        Time complexity: O(n*logn).
        Space complexity: O(1).
        """
        if not intervals:
            return []

        # Sort by interval's start.
        intervals = sorted(intervals)

        # Iterate through intervals to append them or update end. 
        result = [intervals[0]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] > result[-1][1]:
                # If interval is not overlapped with the last, append interval.
                result.append(intervals[i])
            else:
                # If overlapped, update the result's end.
                result[-1][1] = max(intervals[i][1], result[-1][1])

        return result


def main():
    import time

    print 'By naive:'
    start_time = time.time()

    # Ans: [[1,6],[8,10],[15,18]]
    intervals = [[1,3], [2,6], [8,10], [15,18]]
    print SolutionBrute().merge(intervals)

    # Ans: [[1,5]]
    intervals = [[1,4], [4,5]]
    print SolutionBrute().merge(intervals)

    # Ans: [[0, 4]]
    intervals = [[1,4], [0,4]]
    print SolutionBrute().merge(intervals)

    # Ans: [[0,5]]
    intervals = [[1,4], [0,5]]
    print SolutionBrute().merge(intervals)

    # Ans: [[1, 10]]
    intervals = [[2,3], [4,5], [6,7], [8,9], [1,10]]
    print SolutionBrute().merge(intervals)

    print 'Time: {}'.format(time.time() - start_time)

    print 'By checking the last:'
    start_time = time.time()

    # Ans: [[1,6],[8,10],[15,18]]
    intervals = [[1,3], [2,6], [8,10], [15,18]]
    print SolutionSortStartAppendOrUpdateEnd().merge(intervals)

    # Ans: [[1,5]]
    intervals = [[1,4], [4,5]]
    print SolutionSortStartAppendOrUpdateEnd().merge(intervals)

    # Ans: [[0, 4]]
    intervals = [[1,4], [0,4]]
    print SolutionSortStartAppendOrUpdateEnd().merge(intervals)

    # Ans: [[0,5]]
    intervals = [[1,4], [0,5]]
    print SolutionSortStartAppendOrUpdateEnd().merge(intervals)

    # Ans: [[1, 10]]
    intervals = [[2,3], [4,5], [6,7], [8,9], [1,10]]
    print SolutionSortStartAppendOrUpdateEnd().merge(intervals)

    print 'Time: {}'.format(time.time() - start_time)


if __name__ == '__main__':
    main()
{'fraction_non_alphanumeric': 0.15955251439122406, 'fraction_numerical': 0.039752362333007496, 'mean_word_length': 2.0500165617754225, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 9, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2455263', 'n_tokens_mistral': 3090, 'n_tokens_neox': 2847, 'n_words': 719}