각 행이 [start_x, end_x, num_passengers]를 포함하는 요청된_트립이라는 행렬이 있고 용량 값도 있다고 가정합니다. 이제 요청된 각 여행은 start_x에서 num_passengers 승객을 태우고 end_x에서 하차하도록 요청합니다. 우리는 또한 주어진 수용력을 가진 차가 있고 위치 x =0에서 시작합니다. 우리는 모든 승객을 태우고 싶고 오른쪽으로만 이동할 수 있습니다. 우리는 모두를 태우고 내릴 수 있는지 확인해야 합니다.
따라서 입력이 trips =[[1, 25, 2], [3, 4, 3],[5, 12, 3]] capacity =6과 같으면 출력은 True
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이벤트 :=새 목록
-
여행의 각 세트(sx, ex, np)에 대해 수행
-
이벤트 끝에 쌍(sx, np) 삽입
-
이벤트 끝에 쌍(예:-np) 삽입
-
-
나르는 것 :=0
-
이벤트 목록의 각 쌍(loc, delta)에 대해(정렬된 순서로) 다음을 수행하십시오.
-
나르기 :=나르기 + 델타
-
운반하는 경우> 용량, 다음
-
거짓을 반환
-
-
-
참을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, trips, capacity): events = [] for sx, ex, np in trips: events.append((sx, np)) events.append((ex, -np)) carrying = 0 for loc, delta in sorted(events): carrying += delta if carrying > capacity: return False return True ob = Solution() trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6 print(ob.solve(trips, capacity))
입력
trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6
출력
True