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 ++++++++++++++++-----
 1 file changed, 86 insertions(+), 24 deletions(-)

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

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
-- 
cgit v1.2.3