回答編集履歴
1
コード修正
test
CHANGED
|
@@ -2,9 +2,17 @@
|
|
|
2
2
|
|
|
3
3
|
実装コードとしては[C言語 直線状の線分の重複回数を求めるアルゴリズム](https://ja.stackoverflow.com/questions/62057/c%E8%A8%80%E8%AA%9E-%E7%9B%B4%E7%B7%9A%E7%8A%B6%E3%81%AE%E7%B7%9A%E5%88%86%E3%81%AE%E9%87%8D%E8%A4%87%E5%9B%9E%E6%95%B0%E3%82%92%E6%B1%82%E3%82%81%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)が参考になります。
|
|
4
4
|
|
|
5
|
-
```Python
|
|
6
5
|
|
|
7
6
|
|
|
7
|
+
> その範囲を計算したい
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
タイトル見逃していました。重なる範囲も得られるようにしました。
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
```Python
|
|
8
16
|
|
|
9
17
|
from collections import namedtuple
|
|
10
18
|
|
|
@@ -52,15 +60,15 @@
|
|
|
52
60
|
|
|
53
61
|
# 端点データのセットアップ
|
|
54
62
|
|
|
55
|
-
End = namedtuple('end', ('x', 'isLeft'))
|
|
63
|
+
End = namedtuple('end', ('x', 'isLeft', 'srcPos'))
|
|
56
64
|
|
|
57
65
|
ends = []
|
|
58
66
|
|
|
59
|
-
for hani in hani_list:
|
|
67
|
+
for i, hani in enumerate(hani_list):
|
|
60
68
|
|
|
61
|
-
ends.append( End(hani[0], True))
|
|
69
|
+
ends.append( End(hani[0], True, i))
|
|
62
70
|
|
|
63
|
-
ends.append( End(hani[1], False))
|
|
71
|
+
ends.append( End(hani[1], False,i))
|
|
64
72
|
|
|
65
73
|
|
|
66
74
|
|
|
@@ -76,23 +84,37 @@
|
|
|
76
84
|
|
|
77
85
|
currentOverlaps = 0
|
|
78
86
|
|
|
87
|
+
curRanges = set()
|
|
88
|
+
|
|
89
|
+
maxRanges = set()
|
|
90
|
+
|
|
79
91
|
for end in ends:
|
|
80
92
|
|
|
81
93
|
if end.isLeft:
|
|
82
94
|
|
|
83
95
|
currentOverlaps += 1
|
|
84
96
|
|
|
97
|
+
curRanges.add(end.srcPos)
|
|
98
|
+
|
|
85
99
|
if currentOverlaps > maxOverlaps:
|
|
86
100
|
|
|
87
101
|
maxOverlaps = currentOverlaps
|
|
102
|
+
|
|
103
|
+
maxRanges = curRanges.copy()
|
|
88
104
|
|
|
89
105
|
else:
|
|
90
106
|
|
|
91
107
|
currentOverlaps -= 1
|
|
92
108
|
|
|
109
|
+
curRanges.remove(end.srcPos)
|
|
93
110
|
|
|
94
111
|
|
|
112
|
+
|
|
113
|
+
maxRanges = [hani_list[n] for n in sorted(maxRanges)]
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
95
|
-
return maxOverlaps
|
|
117
|
+
return maxOverlaps, maxRanges
|
|
96
118
|
|
|
97
119
|
|
|
98
120
|
|
|
@@ -100,7 +122,7 @@
|
|
|
100
122
|
|
|
101
123
|
ret = getMaxOverlaps( hani_list)
|
|
102
124
|
|
|
103
|
-
print(ret) # 6
|
|
125
|
+
print(ret) # (6, [[-1.0, 20.0], [0.0, 14.0], [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]])
|
|
104
126
|
|
|
105
127
|
|
|
106
128
|
|
|
@@ -108,6 +130,6 @@
|
|
|
108
130
|
|
|
109
131
|
ret = getMaxOverlaps( hani_list)
|
|
110
132
|
|
|
111
|
-
print(ret) # 2
|
|
133
|
+
print(ret) # (2, [[1, 2], [2, 3]])
|
|
112
134
|
|
|
113
135
|
```
|