From 88a15736625e2847d5c479ceabf202ea6be1e75b Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 9 Dec 2018 19:23:30 -0600
Subject: Organize lottery done.

It wasn't hard since I worked this out in Java first. Once again, I felt
Python is really well designed and efficient.---
 .../sources/points_segments.py                     | 52 ++++++++++++++++++++++
 .../tests/points_segmentsTest.py                   | 24 ++++++++++
 2 files changed, 76 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/points_segments.py
 create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/points_segmentsTest.py

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/points_segments.py b/AlgoDesignAndTechniqueEdxPython/sources/points_segments.py
new file mode 100644
index 0000000..780d8da
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/points_segments.py
@@ -0,0 +1,52 @@
+# Uses python3
+import sys
+from collections import namedtuple
+
+Segment = namedtuple('Segment', 'start end')
+
+
+def fast_count_segments(starts, ends, points):
+    # https://www.coursera.org/learn/algorithmic-toolbox/discussions/all/threads/QJ1jK9wNEeWdPBL2iFTrAw/replies/Ihiw4txhEeWK5g7mfcS2Xw/comments/oyAMaeIiEeWyqwpvChh66Q
+    # I'm following the algo described above. I've worked it out using Java already
+    # l->1, p->2, r->3
+    index = 0
+    segments = []
+    tempPointAndIndex = []
+    while index < len(starts):
+        segments.append(Segment(starts[index], 1))
+        segments.append(Segment(ends[index], 3))
+        index = index + 1
+    index = 0
+    while index < len(points):
+        segments.append(Segment(points[index], 2))
+        tempPointAndIndex.append(Segment(points[index], index))
+        index = index + 1
+    segments.sort()
+    tempPointAndIndex.sort()
+    results = []
+    count = 0
+    for i in range(len(segments)):
+        if segments[i].end == 1:
+            count = count + 1
+        if segments[i].end == 2:
+            results.append(count)
+        if segments[i].end == 3:
+            count = count - 1
+    finalResults = [0] * len(points)
+    for i in range(len(results)):
+       finalResults[tempPointAndIndex[i].end] = results[i] 
+    return finalResults
+
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    data = list(map(int, input.split()))
+    n = data[0]
+    m = data[1]
+    starts = data[2:2 * n + 2:2]
+    ends = data[3:2 * n + 2:2]
+    points = data[2 * n + 2:]
+    # use fast_count_segments
+    cnt = fast_count_segments(starts, ends, points)
+    for x in cnt:
+        print(x, end=' ')
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/points_segmentsTest.py b/AlgoDesignAndTechniqueEdxPython/tests/points_segmentsTest.py
new file mode 100644
index 0000000..1a0f229
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/points_segmentsTest.py
@@ -0,0 +1,24 @@
+'''
+Created on Dec 9, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.points_segments import fast_count_segments
+
+class Test(unittest.TestCase):
+
+
+    def testName(self):
+        starts = [0, 7]
+        ends = [5, 10]
+        points = [1, 6, 11]
+        results = [1, 0, 0]
+        self.assertSequenceEqual(results, fast_count_segments(starts, ends, points))
+        
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file
-- 
cgit v1.2.3