summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-09 19:23:30 -0600
committerHaidong Ji2018-12-09 19:23:30 -0600
commit88a15736625e2847d5c479ceabf202ea6be1e75b (patch)
tree3894b1e1b3ff9f873db2c60d54fc9fee575fbe80
parent886e0deedbaf1a53bbd6c37fac4337b80d30cae8 (diff)
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.
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/points_segments.py52
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/points_segmentsTest.py24
2 files changed, 76 insertions, 0 deletions
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