diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/points_segments.py | 52 | ||||
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/tests/points_segmentsTest.py | 24 |
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 |