You are driving a vehicle that has capacity empty seats initially available for passengers.  The vehicle only drives east (ie. it cannot turn around and drive west.)
Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off.  The locations are given as the number of kilometers due east from your vehicle's initial location.
Return true if and only if it is possible to pick up and drop off all passengers for all the given trips. 
 
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false


Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true


Example 3:
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true


Example 4:
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true







 



 
Constraints:

trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Range queries

Starter code: class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        

Solutions:
class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		d = defaultdict(int)
		for (a, b, c) in trips:
			d[b] += a
			d[c] -= a
		k = 0
		for t in sorted(d.keys()):
			k += d[t]
			if k > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		from collections import defaultdict
		log = defaultdict(int)
		for (num, start, end) in trips:
			log[start] += num
			log[end] -= num
		on_bus = 0
		for stop in sorted(log.keys()):
			on_bus += log[stop]
			if on_bus > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		timestamp = []
		for trip in trips:
			timestamp.append([trip[1], trip[0]])
			timestamp.append([trip[2], -trip[0]])
		timestamp.sort()
		used_capacity = 0
		for (time, passenger_change) in timestamp:
			used_capacity += passenger_change
			if used_capacity > capacity:
				return False
		return True


from queue import PriorityQueue

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		sorted_trips = sorted(trips, key=lambda x: (x[1], x[2]))
		pq = PriorityQueue()
		total_pnum = 0
		for trip in sorted_trips:
			(pnum, start_loc, end_loc) = (trip[0], trip[1], trip[2])
			total_pnum += pnum
			while pq.qsize() > 0:
				(prev_end_loc, prev_pnum) = pq.get()
				if prev_end_loc > start_loc:
					pq.put((prev_end_loc, prev_pnum))
					break
				total_pnum -= prev_pnum
			if end_loc > start_loc:
				pq.put((end_loc, pnum))
			if total_pnum > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		passenger = 0
		onboard = defaultdict(int)
		offboard = defaultdict(int)
		for t in trips:
			onboard[t[1]] += t[0]
			offboard[t[2]] += t[0]
		for d in range(10001):
			if d in onboard:
				passenger += onboard[d]
			if d in offboard:
				passenger -= offboard[d]
			if passenger > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		if not trips or len(trips) == 0 or capacity == 0:
			return False
		trips.sort(key=lambda x: x[1])
		arr = []
		for (num, start, end) in trips:
			arr.append([start, num])
			arr.append([end, -num])
		arr.sort(key=lambda x: x[0])
		total = 0
		for a in arr:
			total += a[1]
			if total > capacity:
				return False
		return True


from queue import PriorityQueue

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		if len(trips) == 0:
			return True
		pq = PriorityQueue()
		total_pnum = 0
		for trip in trips:
			pq.put((trip[1], trip[0]))
			pq.put((trip[2], -trip[0]))
		while pq.qsize() > 0:
			(cur_loc, pnum) = pq.get()
			total_pnum += pnum
			if total_pnum > capacity:
				return False
		return True


from collections import defaultdict

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		d = defaultdict(int)
		for (n, s, e) in trips:
			d[s] += n
			d[e] -= n
		cur = 0
		for k in sorted(d):
			cur += d[k]
			if cur > capacity:
				return False
		return True


import heapq

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		for (i, v) in sorted((x for (n, i, j) in trips for x in [[i, n], [j, -n]])):
			capacity -= v
			if capacity < 0:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], c: int) -> bool:
		(f, t) = (float('inf'), -1)
		b = collections.defaultdict(int)
		for (n, s, e) in trips:
			b[s] += n
			b[e] -= n
			f = min(f, s)
			t = max(t, e)
		for i in range(f, t + 1):
			b[i] += b[i - 1]
			if b[i] > c:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips_pickup = sorted(trips, key=lambda x: x[1])
		trips_drop = sorted(trips, key=lambda x: x[2])
		passengers = 0
		i = 0
		j = 0
		while i < len(trips):
			if trips_pickup[i][1] < trips_drop[j][2]:
				passengers += trips_pickup[i][0]
			else:
				passengers -= trips_drop[j][0]
				j += 1
				continue
			i += 1
			if passengers > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips = sorted(trips, key=lambda x: x[1])
		currentPassengerCt = trips[0][0]
		tripList = dict()
		tripList[trips[0][2]] = trips[0][0]
		for idx in range(1, len(trips)):
			numPassengers = trips[idx][0]
			startPt = trips[idx][1]
			endPt = trips[idx][2]
			for prevEndPoint in sorted(tripList.keys()):
				if startPt >= prevEndPoint:
					currentPassengerCt -= tripList[prevEndPoint]
					del tripList[prevEndPoint]
			if endPt in tripList:
				tripList[endPt] += numPassengers
			else:
				tripList[endPt] = numPassengers
			currentPassengerCt += numPassengers
			if currentPassengerCt > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trip_travel = []
		for (passengers, start, end) in trips:
			trip_travel.append((start, passengers, 1))
			trip_travel.append((end, passengers, 0))
		trip_travel.sort(key=lambda x: (x[0], x[2]))
		for travel in trip_travel:
			if travel[2] == 1:
				capacity -= travel[1]
			else:
				capacity += travel[1]
			if capacity < 0:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		import numpy as np
		timestamp = np.zeros(1001)
		for trip in trips:
			timestamp[trip[1]:] += trip[0]
			timestamp[trip[2]:] -= trip[0]
		if max(timestamp) > capacity:
			return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

		def Sort(sub_li):
			sub_li.sort(key=lambda x: x[1])
			return sub_li
		trips = Sort(trips)
		people = 0
		on_board = []
		for [n, a, b] in trips:
			people += n
			while on_board and on_board[0][1] <= a:
				t = on_board.pop(0)
				people -= t[0]
			if people > capacity:
				return False
			on_board.append([n, b])
			on_board = Sort(on_board)
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		if not trips:
			return 0
		tmp = sorted((x for (v, i, j) in trips for x in [[i, v], [j, -v]]))
		n = 0
		for (_, v) in tmp:
			n += v
			if n > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips.sort(key=lambda x: x[1])
		(capacity_needed, hp) = (0, [])
		for trip in trips:
			while hp and hp[0][0] <= trip[1]:
				(end, start, c) = heapq.heappop(hp)
				capacity_needed -= c
			capacity_needed += trip[0]
			if capacity_needed > capacity:
				return False
			heapq.heappush(hp, (trip[2], trip[1], trip[0]))
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips.sort(key=lambda x: x[1])
		print(trips)
		start = trips[0][1]
		end = trips[0][2]
		capacity = capacity - trips[0][0]
		if capacity < 0:
			return False
		q = [(trips[0][2], trips[0][0])]
		n = len(trips)
		for trip in trips[1:]:
			s = trip[1]
			dup = q[:]
			while q:
				if q[0][0] <= s:
					capacity += q[0][1]
					q.pop(0)
				else:
					break
			capacity -= trip[0]
			q.append((trip[2], trip[0]))
			q.sort(key=lambda x: x[0])
			if capacity < 0:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips = sorted(trips, key=lambda x: x[1])
		cap = capacity
		st = []
		for trip in trips:
			if not st:
				if cap < trip[0]:
					return False
				st.append((trip[0], trip[-1]))
				cap -= trip[0]
			else:
				st = sorted(st, key=lambda x: x[1])
				while st and trip[1] >= st[0][1]:
					cap += st[0][0]
					st.pop(0)
				if cap < trip[0]:
					return False
				st.append((trip[0], trip[-1]))
				cap -= trip[0]
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips.sort(key=lambda x: x[1])
		length = len(trips)
		count = 0
		queue = []
		for trip in trips:
			(num_passengers, start_location, end_location) = trip
			while queue and queue[0][2] <= start_location:
				count -= queue[0][0]
				queue = queue[1:]
			queue.append(trip)
			queue.sort(key=lambda x: x[2])
			count += num_passengers
			if count > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		r = True
		active = []
		currContent = 0
		maxCapacity = 0
		time = 0
		trips.sort(key=lambda x: x[1])
		lenTrips = len(trips)
		for i in range(0, lenTrips):
			time = trips[i][1]
			currContent += trips[i][0]
			active.append(i)
			for j in range(len(active) - 1, -1, -1):
				if trips[active[j]][2] <= time:
					currContent -= trips[active[j]][0]
					active.pop(j)
			maxCapacity = max(maxCapacity, currContent)
			if maxCapacity > capacity:
				r = False
				break
		return r


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		sorted_trips = sorted(trips, key=lambda x: x[1])
		in_trip = [sorted_trips[0]]
		cap = capacity - sorted_trips[0][0]
		cur_time = 0
		i = 1
		while i < len(sorted_trips):
			waiting_passenger = sorted_trips[i]
			if not in_trip:
				cap -= waiting_passenger[0]
				in_trip.append(waiting_passenger)
				i += 1
			else:
				first_passenger = in_trip[0]
				if waiting_passenger[1] >= first_passenger[2]:
					in_trip.pop(0)
					cap += first_passenger[0]
				elif cap >= waiting_passenger[0]:
					cap -= waiting_passenger[0]
					in_trip.append(waiting_passenger)
					in_trip = sorted(in_trip, key=lambda x: x[2])
					i += 1
				else:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		sorted_trips = sorted(trips, key=lambda x: x[1])
		print(sorted_trips)
		cur_capacity = 0
		left = 0
		location = [0 for i in range(1000 + 1)]
		for trip in trips:
			new_capacity = trip[0]
			(new_start, new_end) = (trip[1], trip[2])
			location[new_start:new_end] = [cap + new_capacity for cap in location[new_start:new_end]]
		for loc in location:
			if loc > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		ind = 0
		for (a, b, c) in trips:
			ind = max(ind, b, c)
		res = [0] * (ind + 1)
		for (a, b, c) in trips:
			for i in range(b, c):
				res[i] += a
		return not any([x > capacity for x in res])


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

		def add_list(pool, start, end, num):
			for idx in range(start, end):
				pool[idx] += num
		pool = [0] * 1000
		for trip in trips:
			(num, start, end) = trip
			add_list(pool, start, end, num)
		if max(pool) > capacity:
			return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		occupied = [0 for i in range(1001)]
		for (num_passengers, start_location, end_location) in trips:
			for i in range(start_location, end_location):
				occupied[i] += num_passengers
		return max(occupied) <= capacity


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		end = 0
		for (_, _, e) in trips:
			end = max(end, e)
		dp = [0 for _ in range(end)]
		for (passengers, start, end) in trips:
			for i in range(start, end):
				dp[i] += passengers
		return max(dp) <= capacity


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		lst = []
		for (people, st, end) in trips:
			lst.append((st, people, 1))
			lst.append((end, people, 0))
		lst.sort(key=lambda x: (x[0], x[2]))
		current = 0
		for (time, people, pickup) in lst:
			if pickup:
				current += people
			else:
				current -= people
			if current > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		buckets = [0] * 1001
		for trip in trips:
			(passengers, start, end) = trip
			for i in range(start, end):
				buckets[i] += passengers
		for elem in buckets:
			if elem > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		self.remainSeats = capacity
		self.tripsOnBoard = []
		trips = sorted(trips, key=lambda trip: trip[1])
		for trip in trips:
			self.offBoard(trip[1])
			if not self.onBoardTrip(trip):
				return False
		return True

	def offBoard(self, currentLocation: int):
		trips2OffBoard = [trip for trip in self.tripsOnBoard if trip[2] <= currentLocation]
		for trip in trips2OffBoard:
			self.remainSeats += trip[0]
		self.tripsOnBoard = [trip for trip in self.tripsOnBoard if trip[2] > currentLocation]

	def onBoardTrip(self, trip: List[int]) -> bool:
		if trip[0] <= self.remainSeats:
			self.remainSeats -= trip[0]
			self.tripsOnBoard.append(trip)
			return True
		else:
			return False


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		ends = [i[2] for i in trips]
		max_ends = max(ends)
		all_stops = [0 for i in range(0, max_ends + 1)]
		for trip in trips:
			(l, r) = (trip[1], trip[2])
			all_stops[l:r] = [i + trip[0] for i in all_stops[l:r]]
			if max(all_stops[l:r]) > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		final = 0
		for trip in trips:
			final = max(final, trip[2])
		people = [0] * (final + 1)
		for trip in trips:
			for board in range(trip[1], trip[2]):
				people[board] += trip[0]
		if max(people) > capacity:
			return False
		else:
			return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		total_trip = [0 for _ in range(1000)]
		for tt in trips:
			for loc in range(tt[1], tt[2]):
				total_trip[loc] += tt[0]
		if max(total_trip) <= capacity:
			return True
		return False


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		dests = [x[2] for x in trips]
		myl = [0 for i in range(max(dests) + 1)]
		for x in trips:
			for c in range(x[1], x[2]):
				myl[c] += x[0]
		for i in myl:
			if i > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		n = len(trips)
		sorted_trips = sorted(trips, key=lambda t: t[1])
		min_idx = sorted_trips[0][1]
		max_idx = max([t[2] for t in sorted_trips])
		merged = [0 for _ in range(max_idx + 1)]
		for (num_passenger, start_idx, end_idx) in sorted_trips:
			for idx in range(start_idx, end_idx):
				merged[idx] += num_passenger
				if merged[idx] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips = sorted(trips, key=lambda x: x[1])
		curr = []
		for i in trips:
			curr.append([i[0], i[2]])
			s = 0
			for c in curr:
				if c[1] <= i[1]:
					continue
				s += c[0]
			if s > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		d = [0 for i in range(1001)]
		for i in trips:
			for j in range(i[1], i[2]):
				d[j] += i[0]
		for i in range(1001):
			if d[i] > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		pooling = []
		for (num, start, end) in trips:
			pooling.extend([[start, num], [end, -num]])
		pooling.sort()
		for (loc, num) in pooling:
			capacity -= num
			if capacity < 0:
				return False
		return True


from collections import defaultdict, OrderedDict

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips = sorted(trips, key=lambda x: x[1])
		passengers = 0
		dropoffs = defaultdict(int)
		for i in range(len(trips)):
			dropoffs[trips[i][2]] += trips[i][0]
		dropoffs = OrderedDict(sorted(dropoffs.items()))
		for lis in trips:
			passengers += lis[0]
			for key in dropoffs:
				if lis[1] >= key:
					passengers -= dropoffs[key]
					dropoffs[key] = 0
			if passengers > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		load = [0] * 1001
		for (count, from_idx, to_idx) in trips:
			for i in range(from_idx, to_idx):
				load[i] += count
				if load[i] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		passengers = [0] * 1000
		for trip in trips:
			(p, start, end) = trip
			for i in range(start, end):
				passengers[i] += p
				if passengers[i] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		totals = [0] * 1001
		for (passengers, start, end) in trips:
			for x in range(start, end):
				totals[x] += passengers
				if totals[x] > capacity:
					return False
		return True


from operator import itemgetter

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		cp_arr = []
		trips = sorted(trips, key=lambda x: x[1], reverse=False)
		min_val = min([i[1] for i in trips])
		max_val = max([i[2] for i in trips])
		offset = max_val - min_val
		check_arr = [0] * offset
		for trip in trips:
			low = trip[1]
			high = trip[2]
			for i in range(low, high):
				check_arr[i - offset] += trip[0]
		if max(check_arr) <= capacity:
			return True
		return False


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		dp = [capacity] * 1000
		for trip in trips:
			for loc in range(trip[1], trip[2]):
				dp[loc] -= trip[0]
		return not min(dp) < 0


from operator import itemgetter

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		dp = [0] * 1001
		for t in trips:
			for j in range(t[1], t[2]):
				dp[j] += t[0]
				if dp[j] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		count_pass = trips[len(trips) - 1][2] * [0]
		for i in trips:
			if len(count_pass) < i[2]:
				count_pass += [0] * (i[2] - len(count_pass))
			for j in range(i[1], i[2]):
				count_pass[j] += i[0]
				if count_pass[j] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		cap = [capacity] * 1000
		for trip in trips:
			for i in range(trip[1], trip[2]):
				cap[i] -= trip[0]
				if cap[i] < 0:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		if len(trips) <= 0:
			return False
		trips.sort(key=lambda x: x[1])
		stack = []
		if trips[0][0] > capacity:
			return False
		else:
			stack.append(0)
			capacity -= trips[0][0]
		for i in range(1, len(trips)):
			n = 0
			while stack and n < len(stack):
				if trips[i][1] >= trips[stack[n]][2]:
					capacity += trips[stack[n]][0]
					stack.pop(n)
				else:
					n += 1
			if trips[i][0] <= capacity:
				capacity -= trips[i][0]
			elif trips[i][0] > capacity:
				return False
			stack.append(i)
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips = sorted(trips, key=lambda x: x[1])
		pos = 0
		curr_capacity = capacity
		ht = {}
		for trip in trips:
			for prev in ht:
				if prev <= trip[1]:
					curr_capacity += ht[prev]
					ht[prev] = 0
			if trip[0] > curr_capacity:
				return False
			if trip[2] not in ht:
				ht[trip[2]] = trip[0]
			else:
				ht[trip[2]] += trip[0]
			curr_capacity -= trip[0]
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		list_curr = [0] * 1000
		for trip in trips:
			for _ in range(trip[1], trip[2]):
				list_curr[_] += trip[0]
			if max(list_curr) > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trip_start = min([trip[1] for trip in trips])
		trip_end = max([trip[2] for trip in trips])
		trip_register = [0] * (trip_end + 1)
		for trip in trips:
			for idx in range(trip[1], trip[2]):
				trip_register[idx] += trip[0]
		return capacity >= max(trip_register)


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		m = [0 for i in range(1000)]
		for x in trips:
			if x[0] > capacity:
				return False
			for i in range(x[1], x[2]):
				m[i] += x[0]
			if max(m) > capacity:
				return False
		if max(m) > capacity:
			return False
		return True


import heapq

class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		path = [0] * 1001
		for t in trips:
			for i in range(t[1], t[2]):
				path[i] += t[0]
				if path[i] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		pickups = sorted([lst[:2] for lst in trips], key=lambda lst: lst[1])
		dropoffs = sorted([lst[::2] for lst in trips], key=lambda lst: lst[1])
		print(pickups, dropoffs)
		currentCap = 0
		(i, j) = (0, 0)
		(nextP, nextD) = (pickups[0], dropoffs[0])
		while i < len(pickups):
			if nextP[1] < nextD[1] or not nextD:
				currentCap += nextP[0]
				i += 1
				if i < len(pickups):
					nextP = pickups[i]
				else:
					nextP = None
			elif nextP[1] > nextD[1] or not nextP:
				currentCap -= nextD[0]
				j += 1
				if j < len(dropoffs):
					nextD = dropoffs[j]
				else:
					nextD = None
			else:
				currentCap += nextP[0] - nextD[0]
				i += 1
				j += 1
				if i < len(pickups):
					nextP = pickups[i]
				else:
					nextP = None
				if j < len(dropoffs):
					nextD = dropoffs[j]
				else:
					nextD = None
			print(i, j, currentCap)
			if currentCap > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips.sort(key=lambda x: x[1])
		last_dest = max([x[2] for x in trips])
		curr_pos = 0
		cap_ls = [0] * last_dest
		for i in range(len(trips)):
			for j in range(trips[i][1], trips[i][2]):
				cap_ls[j] += trips[i][0]
		return max(cap_ls) <= capacity


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		ans_dic = [0] * 1000
		for i in trips:
			for j in range(i[1], i[2]):
				if ans_dic[j]:
					ans_dic[j] += i[0]
					if ans_dic[j] > capacity:
						return False
				else:
					ans_dic[j] = i[0]
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		totals = [0] * 1001
		for (passengers, start, end) in trips:
			for x in range(start, end):
				totals[x] += passengers
		return not any([x > capacity for x in totals])


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		n = len(trips)
		dp = [0] * 1000
		for trip in trips:
			(num, s, e) = (trip[0], trip[1], trip[2])
			for i in range(s, e):
				dp[i] += num
		print(dp)
		for i in range(len(dp)):
			if dp[i] > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		milesDict = {}
		for trip in trips:
			passengers = trip[0]
			start = trip[1]
			end = trip[2]
			mile = start
			while mile < end:
				if mile in milesDict:
					milesDict[mile] = milesDict[mile] + passengers
				else:
					milesDict[mile] = passengers
				mile = mile + 1
		if max(milesDict.values()) <= capacity:
			return True
		else:
			return False


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		d = dict()
		ppl = 0
		for i in trips:
			d[i[1]] = d.get(i[1], 0) + i[0]
			for j in range(i[1] + 1, i[2]):
				d[j] = d.get(j, 0) + i[0]
		for i in list(d.values()):
			if i > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		d = {}
		for i in trips:
			for j in range(i[1] + 1, i[2] + 1):
				if j not in d:
					d[j] = i[0]
				else:
					d[j] += i[0]
		for i in d:
			if d[i] > capacity:
				return 0
		return 1


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		kmlist = {}
		trips.sort(key=lambda x: (x[1], x[2]))
		for trip in trips:
			for i in range(trip[1], trip[2]):
				if i in kmlist:
					kmlist[i] += trip[0]
				else:
					kmlist[i] = trip[0]
		maxval = max(kmlist.values())
		return maxval <= capacity


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		events = [[x[1], x[0]] for x in trips] + [[x[2], -x[0]] for x in trips]
		events.sort()
		n = 0
		for event in events:
			n += event[1]
			if n > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		res = [0] * 1000
		for trip in trips:
			(passenger, start, end) = trip
			for i in range(start, end):
				res[i] += passenger
		return max(res) <= capacity


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		if not trips:
			return True
		firstStop = 1001
		lastStop = -1
		for trip in trips:
			firstStop = min(firstStop, trip[1])
			lastStop = max(lastStop, trip[2])
		stops = [0] * (lastStop - firstStop + 1)
		for trip in trips:
			for i in range(trip[1], trip[2]):
				stops[i - firstStop] += trip[0]
				if stops[i - firstStop] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		p_list = list()
		for (p, s, e) in trips:
			if len(p_list) < e:
				p_list += [0] * (e - len(p_list))
			for i in range(s, e):
				p_list[i] += p
				if p_list[i] > capacity:
					return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

		def car_pooling(trips, capacity):
			trips.sort(key=lambda x: x[1])
			timeline = {}
			for trip in trips:
				for t in range(trip[1], trip[2]):
					timeline[t] = timeline.get(t, 0) + trip[0]
			for t in timeline:
				if timeline[t] > capacity:
					return False
			return True
		return car_pooling(trips, capacity)


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		ma = float('-inf')
		trips = sorted(trips, key=lambda v: v[1])
		for i in range(len(trips)):
			tmp = 0
			for j in range(i + 1):
				if trips[j][2] > trips[i][1]:
					tmp += trips[j][0]
			ma = max(tmp, ma)
		return ma <= capacity


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		passIn = [[item[1], item[0]] for item in trips]
		passOut = [[item[2], -item[0]] for item in trips]
		setOfTimes = list(set([item[1] for item in trips] + [item[2] for item in trips]))
		setOfTimes.sort()
		ans = True
		counter = 0
		for time in setOfTimes:
			if ans == True:
				for item in passIn + passOut:
					if item[0] == time:
						counter += item[1]
				if counter > capacity:
					ans = False
		return ans


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		d = {}
		for (passengers, start, end) in trips:
			for i in range(start, end):
				if d.get(i) == None:
					d[i] = passengers
				else:
					d[i] += passengers
		for x in d:
			if d[x] > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		end = 0
		inCar = 0
		for i in range(0, len(trips)):
			if trips[i][2] > end:
				end = trips[i][2]
		for i in range(1, end):
			for item in trips:
				if item[2] == i:
					inCar -= item[0]
				elif item[1] == i:
					inCar += item[0]
			if inCar > capacity:
				return False
		return True


class Solution:

	def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
		trips.sort(key=lambda x: x[1])
		heap = []
		cur = 0
		for (pas, start, end) in trips:
			while heap and heap[0][0] <= start:
				cur -= heappop(heap)[1]
			heappush(heap, (end, pas))
			cur += pas
			if cur > capacity:
				return False
		return True