Q003_rokic_solution

[Rokicto]

Question_ID: Q003

Language: python

Time Cost: 38-mins

Time Complexity: O(n^2)

Solution

My Code

#!/usr/bin/python

def is_common_point_shared(rectangle1, rectangle2):
    """Return if two rectangles share common points"""
    up1, down1, left1, right1 = rectangle1
    up2, down2, left2, right2 = rectangle2

    return not (up1 < down2 or up2 < down1 or left1 > right2 or left2 > right1)

def replace_rectangle(rectangle1, rectangle2):
    """Return a smallest rectangle, which covers the original two"""
    up1, down1, left1, right1 = rectangle1
    up2, down2, left2, right2 = rectangle2

    return [max([up1, up2]), min([down1, down2]),
            min([left1, left2]), max([right1, right2])]

def maximum_rectangle(rectangles):
    """Return a list of 'maximum rectangles'"""
    independent_rectangles = set()

    for next_rectangle in rectangles:
        independ = False

        while not independ:
            independ = True

            for rec in independent_rectangles:
                if is_common_point_shared(next_rectangle, rec):
                    next_rectangle = replace_rectangle(next_rectangle, rec)
                    independent_rectangles.discard(rec)

                    independ = False

                    break

        independent_rectangles.add(tuple(next_rectangle))

    return list(map(list, independent_rectangles))

Unit Tests

import unittest

from Q003 import maximum_rectangle

class MaximumRectangeTest(unittest.TestCase):
    """Tests for maximum_rectangle"""

    def assertEqual(self, first, second, msg=None):
        """Check if 'equals'"""
        if not set(map(tuple, first)) == set(map(tuple, second)):
            raise self.failureException(msg)

    def test_case1(self):
        """case1"""
        args = [[1, 0, 0, 1],
                [1, 0, 4, 5],
                [3, 2, 2, 5],
                [2, 1, 5, 6]]
        expected = [[1, 0, 0, 1], [3, 0, 2, 6]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case2(self):
        """case2"""
        args = [[5, -5, 3, 8],
                [2, -1, 4, 5]]
        expected = [[5, -5, 3, 8]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case3(self):
        """case3"""
        args = [[7, 6, 2, 7],
                [5, -1, 6, 8],
                [2, -3, -1, 4],
                [10, 4, -3, 1]]
        expected = [[7, 6, 2, 7], [5, -1, 6, 8],
                    [2, -3, -1, 4], [10, 4, -3, 1]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case4(self):
        """case4"""
        args = [[7, 6, 2, 7],
                [20, 1, 5, 6],
                [15, 4, 8, 15],
                [12, 10, 10, 20]]
        expected = [[15, 4, 8, 20], [20, 1, 2, 7]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case5(self):
        """case5"""
        args = [[1, 0, 2, 3],
                [0, -3, -1, 2]]
        expected = [[1, -3, -1, 3]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case6(self):
        """case6"""
        args = [[6, 3, -5, -2],
                [5, -3, 1, 6],
                [2, -1, -4, 2]]
        expected = [[6, -3, -5, 6]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

if __name__ == '__main__':
    unittest.main()

Other

[rbee3u]

单元测试小王子受我一拜，另外你这复杂度是O(n^2)的不是三次方，帮你改了，很漂亮的解法