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 ++++++++++++++++++++++
 1 file changed, 52 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/points_segments.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources/points_segments.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=' ')
-- 
cgit v1.2.3