From 38b3f4b27cb5141f27e81d1f66082af7a2e9cfbb Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Wed, 19 Sep 2018 21:45:59 -0500 Subject: Covering segment complete. This is quite tricky. I read the forum and it helped https://courses.edx.org/courses/course-v1:UCSanDiegoX+ALGS200x+2T2017/discussion/forum/course/threads/5a427c497acf2d0810000713 In particular try_my_best's algorithm worked. But I need to de-dup and sort the list before feeding it to that algorithm, otherwise it won't pass all the tests!--- .../sources/covering_segment.py | 110 +++++++++++---- .../tests/covering_segmentsTest.py | 155 ++++++++++++++++++--- 2 files changed, 224 insertions(+), 41 deletions(-) diff --git a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py index 1093565..b083e31 100644 --- a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py +++ b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py @@ -5,29 +5,91 @@ from collections import namedtuple Segment = namedtuple('Segment', 'start end') -def getSortedListOfSegs(segList): - segList.sort() - return segList +# def getSortedListOfSegs(segList): +# segList.sort() +# return segList +# +# +# def getOptimalPoints(segList): +# if len(segList) == 1: +# return [segList[0].start] +# if segList[0].end <= segList[1].start: +# result = [segList[0].end] +# if segList[1].start == segList[1].end: +# if len(segList) == 2: +# return result +# else: +# result.extend(getOptimalPoints(segList[2:])) +# return result +# else: +# if segList[0].end >= segList[1].end: +# result = [segList[1].end] +# del(segList[1]) +# result.extend(getOptimalPoints(segList[1:])) +# return result +# else: +# result = [segList[0].end] +# result.extend(getOptimalPoints(segList[1:])) +# return result +# +# +# def getOptimalPoints1(segList): +# if len(segList) == 1: +# return [segList[0].start] +# if segList[0] == segList[1]: +# return getOptimalPoints1(segList[1:]) +# if segList[0].start == segList[0].end: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# if segList[0].start == segList[1].start: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# if segList[0].end < segList[1].start: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# else: +# if segList[0].end == segList[1].start: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# else: # segList[0].end > segList[1].start +# if segList[0].end < segList[1].end: +# result = [segList[0].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# if segList[0].end == segList[1].end: +# result = [segList[1].end] +# result.extend(getOptimalPoints1(segList[1:])) +# return result +# else: +# result = [segList[1].end] +# del(segList[1]) +# result.extend(getOptimalPoints1(segList)) +# return result -def getOptimalPoints(segList): - if len(segList) == 1: - return [segList[0].start] - if segList[0].end <= segList[1].start: - result = [segList[0].end] - if segList[1].start == segList[1].end: - if len(segList) == 2: - return result - else: - result.extend(getOptimalPoints(segList[2:])) - return result - else: - if segList[0].end >= segList[1].end: - result = [segList[1].end] - del(segList[1]) - result.extend(getOptimalPoints(segList[1:])) - return result - else: - result = [segList[0].end] - result.extend(getOptimalPoints(segList[1:])) - return result \ No newline at end of file +def getOptimalPoints2(segList): + index = 0 + points = [] + while index < len(segList): + points.append(segList[index].end) + index = index + 1 + while index < len(segList) and segList[index].start <= points[-1]: + if segList[index].end < points[-1]: + points[-1] = segList[index].end + index = index + 1 + return points + +if __name__ == '__main__': + input = sys.stdin.read() + n, *data = map(int, input.split()) + segments = set(map(lambda x: Segment(x[0], x[1]), zip(data[::2], data[1::2]))) + segments = list(segments) + segments.sort() + points = getOptimalPoints2(segments) + print(len(points)) + for p in points: + print(p, end=' ') \ No newline at end of file diff --git a/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py index 2d61601..aeb4f36 100644 --- a/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py +++ b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py @@ -7,29 +7,31 @@ import unittest from collections import namedtuple -from sources.covering_segment import getSortedListOfSegs, getOptimalPoints +# from sources.covering_segment import getOptimalPoints, getOptimalPoints1, getOptimalPoints2 +from sources.covering_segment import getOptimalPoints2 Segment = namedtuple('Segment', 'start end') class Test(unittest.TestCase): - def testNameSegment(self): - s1 = Segment(1,2) - self.assertEqual(s1.start, 1) - self.assertEqual(s1.end, 2) +# def testNameSegment(self): +# s1 = Segment(1,2) +# self.assertEqual(s1.start, 1) +# self.assertEqual(s1.end, 2) - def testGetSortedListOfSegs1(self): - s1 = Segment(3,4) - s2 = Segment(1,2) - segList = [s1, s2] - self.assertEqual(getSortedListOfSegs(segList), [s2, s1]) +# def testGetSortedListOfSegs1(self): +# s1 = Segment(3,4) +# s2 = Segment(1,2) +# segList = [s1, s2] +# self.assertEqual(getSortedListOfSegs(segList), [s2, s1]) +# +# def testGetSortedListOfSegs2(self): +# s1 = Segment(3,8) +# s2 = Segment(3,5) +# segList = [s1, s2] +# self.assertEqual(getSortedListOfSegs(segList), [s2, s1]) - def testGetSortedListOfSegs2(self): - s1 = Segment(3,8) - s2 = Segment(3,5) - segList = [s1, s2] - self.assertEqual(getSortedListOfSegs(segList), [s2, s1]) def testGetOptimalPoints(self): s1 = Segment(1,3) @@ -37,7 +39,7 @@ class Test(unittest.TestCase): s3 = Segment(3,6) segList = [s1, s2, s3] segList.sort() - result = getOptimalPoints(segList) + result = getOptimalPoints2(segList) self.assertEqual(len(result), 1) def testGetOptimalPoints1(self): @@ -47,9 +49,128 @@ class Test(unittest.TestCase): s4 = Segment(5,6) segList = [s1, s2, s3, s4] segList.sort() - result = getOptimalPoints(segList) + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints2(self): + s1 = Segment(1,1) + s2 = Segment(1,1) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints3(self): + s1 = Segment(1,1) + s2 = Segment(1,2) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints4(self): + s1 = Segment(5,6) + s2 = Segment(3,4) + s3 = Segment(1,2) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 3) + + def testGetOptimalPoints5(self): + s1 = Segment(1,1) + s2 = Segment(2,2) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints6(self): + s1 = Segment(1,5) + s2 = Segment(2,2) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints7(self): + s1 = Segment(1,5) + s2 = Segment(2,4) + s3 = Segment(1,3) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints8(self): + s1 = Segment(1,4) + s2 = Segment(2,4) + s3 = Segment(1,3) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints9(self): + s1 = Segment(1,7) + s2 = Segment(1,6) + s3 = Segment(1,3) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints10(self): + s1 = Segment(1,7) + s2 = Segment(1,6) + s3 = Segment(1,3) + s4 = Segment(7,7) + segList = [s1, s2, s3, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints11(self): + s1 = Segment(1,2) + s2 = Segment(3,4) + s3 = Segment(6,12) + s4 = Segment(7,8) + segList = [s1, s2, s3, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 3) + + def testGetOptimalPoints12(self): + s1 = Segment(1,15) + s2 = Segment(2,14) + s3 = Segment(6,12) + s4 = Segment(7,8) + segList = [s1, s2, s3, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints13(self): + s1 = Segment(1,15) + s2 = Segment(2,3) + s4 = Segment(4,8) + segList = [s1, s2, s4] + segList.sort() + result = getOptimalPoints2(segList) self.assertEqual(len(result), 2) + def testGetOptimalPoints14(self): + s1 = Segment(1,3) + s2 = Segment(1,4) + s4 = Segment(2,3) + segList = [s1, s2, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) if __name__ == "__main__": #import sys;sys.argv = ['', 'Test.testName'] -- cgit v1.2.3