Does the Shuttle Fit Everyone?

A shuttle drives along a line of numbered stops, always forward. Each trip trips[i] = [riders, board, alight] means riders people board at stop board and leave at stop alight (board < alight). People leaving at a stop get off before anyone boards there. The shuttle holds at most capacity people. Return True if every trip can be served, False otherwise.

Examples

Input:  trips = [[3, 0, 4], [2, 2, 6], [4, 4, 7]], capacity = 5
Output: False
Explanation: at stop 4 the first group leaves, but 2 + 4 = 6 riders remain, exceeding 5.

Input:  trips = [[3, 0, 4], [2, 2, 6], [4, 4, 7]], capacity = 6
Output: True

Input:  trips = [], capacity = 1
Output: True

Constraints

• 0 <= len(trips) <= 10**5, 1 <= riders <= 100, 1 <= capacity <= 10**7
• 0 <= board < alight <= 10**5
• Target complexity: O(n + S) where S is the largest stop number. Adding each trip to every stop it covers is too slow.

Goals

• Convert boarding and alighting events into a difference array
• Track the running load and compare against a capacity