MaxNonoverlappingSegments
🔗 質問リンク
https://app.codility.com/programmers/lessons/16-greedy_algorithms/max_nonoverlapping_segments/start/
問題の説明
Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B I . The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.
Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].
We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.
For example, consider arrays A, B such that:
A[0] = 1 B[0] = 5
A[1] = 3 B[1] = 6
A[2] = 7 B[2] = 8
A[3] = 9 B[3] = 9
A[4] = 9 B[4] = 10
The segments are shown in the figure below.The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.
Write a function:
def solution(A, B)
that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.
For example, given arrays A, B shown above, the function should return 3, as explained above.
⚠▼制限
N is an integer within the range [0..30,000];
each element of arrays A, B is an integer within the range [0..1,000,000,000];
A[I] ≤ B[I], for each I (0 ≤ I < N);
B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).
💡 プール(言語:Python)
方法が思いつかない.人の解答を学びました.意外なことに、これは難しくない直観的な解答です.コアは、終点、第1点を基準に並べ替え、前の終点と後ろの始点を比較してカウントします.
def solution(A, B):
n = len(A)
lis = []
# 길이가 0, 1인 경우는 아래 코드에서 처리 못함
if n == 0:
return 0
elif n == 1:
return 1
# 시작, 끝 위치를 튜플로 묶어서 리스트에 넣어줌
for a, b in zip(A, B):
lis.append((a, b))
# 먼저 끝점 기준 그 다음으로 시작점 기준으로 정렬
lis.sort(key = lambda x : (x[1], x[0]))
# 처음 스타트 줄
end = lis[0][1]
count = 1
# 끝 점이 다음 줄의 시작 점보다 작으면 조건 만족
for i in range(1, n):
if end < lis[i][0]:
end = lis[i][1]
count += 1
return count
Reference
この問題について(MaxNonoverlappingSegments), 我々は、より多くの情報をここで見つけました https://velog.io/@shiningcastle/MaxNonoverlappingSegmentsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol