n개의 항공편이 있고 1에서 n까지 레이블이 지정되어 있다고 가정합니다. 항공권 예약 목록이 있습니다. i 번째 예약은 예약[i] =[i, j, k]을 사용함을 나타냅니다. 이는 i에서 j까지 포함된 레이블이 지정된 항공편에서 k개의 좌석을 예약했음을 의미합니다. 각 항공편에 예약된 좌석 수를 레이블 순서로 표시하여 길이가 n인 배열 답을 찾으십시오. 따라서 입력이 [[1,2,10],[2,3,20],[2,5,25]]이고 n =5이면 출력은 [10, 55, 45, 25, 25].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- res :=크기가 n인 배열 하나를 만들고 0으로 채웁니다.
- 예약의 각 항목 i에 대해
- res[i[0] - 1] :=res[i[0] - 1] + i[2]
- i[1]
- 1 ~ n – 1 범위의 i에 대해
- res[i] :=res[i] + res[i - 1]
- 반환 결과
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def corpFlightBookings(self, bookings, n): res = [0 for i in range(n)] for i in bookings: res[i[0]-1]+=i[2] if(i[1]<n): res[i[1]]-=i[2] for i in range(1,n): res[i]+=res[i-1] return res ob = Solution() print(ob.corpFlightBookings([[1,2,10],[2,3,20],[2,5,25]],5))
입력
[[1,2,10],[2,3,20],[2,5,25]] 5
출력
[10, 55, 45, 25, 25]