구간 및 (sweep line/line sweep)

sweep line/line sweep의 개요

만약 k개의 Query가 주어진다면, 이 Query는 어떤 길이의 N의 배열 구간에 일정한 값을 더하면, 이 알고리즘은 O(n+k)를 통해 이 배열의 끝 상태를 계산할 수 있다.예를 들어 A의 배열이 존재하고 [i, j]의 구간에 k개에 m을 더한 [i, j, m]의 Query가 있는 경우 먼저 0으로 초기화한 길이로 A보다 한 개 큰 배열 B를 준비한다. 모든 Query에 대해 B[i]에 m을 더하고 B[j+1]에서 m를 뺀 다음에 앞에서 누적과 마지막 요소의 대답을 생략한다.중요한 건 누적화의 아종이죠.Segment Tree 또는 Binary Index Tree 를 사용할 수 있다면 더욱 좋습니다.

예제

370. Range Addition

문제는 상부의 대강에 따라 처리한다1109. Corporate Flight Bookings도 대체로 같은 문제다.

def getModifiedArray(length, updates)
    ans = [0] * (length + 1)
    for i, j, k in updates:
        ans[i] += k
        ans[j+1] -= k
    for i in range(1, length):
        ans[i] += ans[i - 1]
    return ans[:-1]

"""

1094. Car Pooling

차 한 대의capacity와 구간별 승차인원 tripps(<=1000), k: 승차인원, i:pick up인 곳, jdrop off인 곳은 사실상 모든 승차구간에서 승차할 수 있는가.

def carPooling(trips, capacity):
    nums = [0] * 1001 
    for n, i, j in trips:
        nums[i] += n
        nums[j] -= n
    for v in stops:    
        capacity -= v
        if 0 > capacity:
            return False
    return True

1589. Maximum Sum Obtained of Any Permutation

정렬과 구간을 표시하는Query를 제공합니다. 모든 Query의 구간과 최대로 배열할 수 있을 때 최대값을 얻을 수 있습니다.
방침:line sweep수 어느 위치/index 고주파수로 고주파수 순서대로 큰 수를 설정하면 됩니다.

def maxSumRangeQuery(nums, requests):
    n = len(nums)
    cnt = [0] * (n + 1)
    for i, j in req:
        cnt[i] += 1
        cnt[j + 1] -= 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    ans = 0
    for val, num in zip(sorted(cnt[:-1]), sorted(nums)):
        ans += val * num
    return ans % (10**9 + 7)