blob: 780d8dacf33dc69d3ea6aaa56fee613b82534ffb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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=' ')
|
