2 files changed, 89 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py
new file mode 100644
index 0000000..1093565
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py
@@ -0,0 +1,33 @@
+# Uses python3
+import sys
+from collections import namedtuple
+
+Segment = namedtuple('Segment', 'start end')
+
+
+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
+\ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py
new file mode 100644
index 0000000..2d61601
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py
@@ -0,0 +1,56 @@
+'''
+Created on Sep 9, 2018
+
+@author: haidong
+'''
+import unittest
+
+from collections import namedtuple
+
+from sources.covering_segment import getSortedListOfSegs, getOptimalPoints
+
+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 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 testGetOptimalPoints(self):
+        s1 = Segment(1,3)
+        s2 = Segment(2,5)
+        s3 = Segment(3,6)
+        segList = [s1, s2, s3]
+        segList.sort()
+        result = getOptimalPoints(segList)
+        self.assertEqual(len(result), 1)
+
+    def testGetOptimalPoints1(self):
+        s1 = Segment(4,7)
+        s2 = Segment(1,3)
+        s3 = Segment(2,5)
+        s4 = Segment(5,6)
+        segList = [s1, s2, s3, s4]
+        segList.sort()
+        result = getOptimalPoints(segList)
+        self.assertEqual(len(result), 2)
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
+\ No newline at end of file