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!

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']