回答編集履歴
1
コード修正
answer
CHANGED
|
@@ -1,7 +1,11 @@
|
|
|
1
1
|
考え方としては[区間スケジューリング問題の類似問題](https://teratail.com/questions/270817)や[一次元領域の重なり検出のアルゴリズムについての質問です。](https://q.hatena.ne.jp/1206413118)の回答が分かりやすいと思います。
|
|
2
2
|
実装コードとしては[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)が参考になります。
|
|
3
|
+
|
|
4
|
+
> その範囲を計算したい
|
|
5
|
+
|
|
6
|
+
タイトル見逃していました。重なる範囲も得られるようにしました。
|
|
7
|
+
|
|
3
8
|
```Python
|
|
4
|
-
|
|
5
9
|
from collections import namedtuple
|
|
6
10
|
from functools import cmp_to_key
|
|
7
11
|
|
|
@@ -25,11 +29,11 @@
|
|
|
25
29
|
def getMaxOverlaps( hani_list):
|
|
26
30
|
|
|
27
31
|
# 端点データのセットアップ
|
|
28
|
-
End = namedtuple('end', ('x', 'isLeft'))
|
|
32
|
+
End = namedtuple('end', ('x', 'isLeft', 'srcPos'))
|
|
29
33
|
ends = []
|
|
30
|
-
for hani in hani_list:
|
|
34
|
+
for i, hani in enumerate(hani_list):
|
|
31
|
-
ends.append( End(hani[0], True))
|
|
35
|
+
ends.append( End(hani[0], True, i))
|
|
32
|
-
ends.append( End(hani[1], False))
|
|
36
|
+
ends.append( End(hani[1], False,i))
|
|
33
37
|
|
|
34
38
|
# 端点データのソート
|
|
35
39
|
ends = sorted(ends, key=cmp_to_key(compEnds))
|
|
@@ -37,21 +41,28 @@
|
|
|
37
41
|
# 重なりを求める
|
|
38
42
|
maxOverlaps = 0
|
|
39
43
|
currentOverlaps = 0
|
|
44
|
+
curRanges = set()
|
|
45
|
+
maxRanges = set()
|
|
40
46
|
for end in ends:
|
|
41
47
|
if end.isLeft:
|
|
42
48
|
currentOverlaps += 1
|
|
49
|
+
curRanges.add(end.srcPos)
|
|
43
50
|
if currentOverlaps > maxOverlaps:
|
|
44
51
|
maxOverlaps = currentOverlaps
|
|
52
|
+
maxRanges = curRanges.copy()
|
|
45
53
|
else:
|
|
46
54
|
currentOverlaps -= 1
|
|
55
|
+
curRanges.remove(end.srcPos)
|
|
47
56
|
|
|
48
|
-
|
|
57
|
+
maxRanges = [hani_list[n] for n in sorted(maxRanges)]
|
|
49
58
|
|
|
59
|
+
return maxOverlaps, maxRanges
|
|
60
|
+
|
|
50
61
|
hani_list = [[-1.0, 20.0], [0.0, 14.0], [2.0, 3.0], [4.0, 9.0], [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]]
|
|
51
62
|
ret = getMaxOverlaps( hani_list)
|
|
52
|
-
print(ret) # 6
|
|
63
|
+
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]])
|
|
53
64
|
|
|
54
65
|
hani_list = [[1, 2], [2, 3], [3, 4]]
|
|
55
66
|
ret = getMaxOverlaps( hani_list)
|
|
56
|
-
print(ret) # 2
|
|
67
|
+
print(ret) # (2, [[1, 2], [2, 3]])
|
|
57
68
|
```
|