Interval

Interval Overlap Check

729 My Calendar I 731 My Calendar II

interval A (a, b)
interval B (c, d)

if (Math.max(a, c) < Math.min(b, d)) {
    // Overlap
} else {
    // No overlap
}

253 Meeting Rooms II

def minMeetingRooms(self, intervals):
    """
    :type intervals: List[Interval]
    :rtype: int
    """
    intervals.sort(key=lambda interval : interval.start)
    pq = []
    ans = 0
    for interval in intervals:
        while len(pq) > 0 and pq[0] <= interval.start:
            heapq.heappop(pq)
        heapq.heappush(pq, interval.end)
        ans = max(ans, len(pq))
    return ans

Interval Addition

370 Range Addition

// given length, and a list of [startIndex, endIndex, inc]

// A trick is to increment the value of startIndex of the final array by inc, and decrement the value of (endIndex + 1)
// of the final array by inc, such that we can use accumulative sum to get our final answer.

int[] rs = new int[length];
for(int[] range : ranges) {
    int start = range[0];
    int end = range[1];
    int val = range[2];

    rs[start] += val;
    if(end + 1 < length) {
        rs[end + 1] -= val;
    }
}
int sum = 0;
for(int i = 0; i < length; i++) {
    sum += rs[i];
    rs[i] = sum;
}
return rs;