这些是简单的 可以差不多了解一下做法
Maximum Population Year -> 1854
Points That Intersect With Cars -> 2848
Car Pooling -> 1094
My Calendar II -> 731
Shifting Letters II -> 2381
Perfect Rectangle -> 391
Rectangle Area II -> 850
Number of Flowers in Full Bloom -> 2251
这里的会更全面一点
https://leetcode.com/problem-list/mzw3cyy6/
2054. Two Best Non-Overlapping Events
def maxTwoEvents(self, events: List[List[int]]) -> int:
events = sorted(events, key = lambda x:x[0])
ends = []
maxi = 0
max_prev = 0
for start, end, value in events:
while ends and ends[0][0] < start:
_, prev_val = heapq.heappop(ends)
max_prev = max(max_prev, prev_val)
maxi = max(maxi, value + max_prev)
heapq.heappush(ends, (end, value))
return maxi56. Merge Intervals
很经典的题 下面的回头看
If this is an real world abstrcted problem, i’d prefer to use divide and conquer technique depends on the requirements. For example, partitioning input intervals based on interval start/end value, i.e we have 1000 buckets, inside each bucket we maintain a sorted intervals, each bucket can be in one machine or multiples buckets in one machine. then we use merge those bucket 2 by 2 until to the point each bucket contains maximum intervals. And make sure no intervals are across two buckets
For either endless incoming stream mentioned here or memory is too small to load all intervals, this approach should work.
this BST approach is impresive but not realistic for me to write in the interview
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
span = [0] * 10 ** 4 + [0] * 2
ints = []
maxi = 0
start = False
mem = set()
for star, end in intervals:
if star == end:
mem.add(star)
span[star] += 1
span[end] -= 1
maxi = max(maxi, end)
for i in range(maxi+1):
span[i] += span[i-1]
if span[i] and not start:
ints.append([i])
start = True
elif not span[i] and start:
ints[-1].append(i)
start = False
elif i in mem and not start:
ints.append([i, i])
return ints731. My Calendar II
class MyCalendarTwo:
def __init__(self):
self.cal = {}
self.max = 2
def book(self, startTime: int, endTime: int) -> bool:
self.cal[startTime] = self.cal.get(startTime, 0) + 1
self.cal[endTime] = self.cal.get(endTime, 0) - 1
total_act = 0
for time, act in sorted(self.cal.items()):
if time > endTime:
return True
total_act += act
if total_act > self.max:
self.cal[startTime] -= 1
self.cal[endTime] += 1
if self.cal[startTime] == 0:
del self.cal[startTime]
if self.cal[endTime] == 0:
del self.cal[endTime]
return False
return Trueclass MyCalendarTwo:
def __init__(self):
# List of single and double bookings
self.single_bookings = []
self.double_bookings = []
def book(self, start: int, end: int) -> bool:
# Check for any overlap with double bookings (would result in triple booking)
for dbl_start, dbl_end in self.double_bookings:
**if max(start, dbl_start) < min(end, dbl_end):** # If there's an overlap with double bookings
return False
# Check for overlaps with single bookings and prepare to add the overlap to double bookings
for sng_start, sng_end in self.single_bookings:
overlap_start = max(start, sng_start)
overlap_end = min(end, sng_end)
if overlap_start < overlap_end: # There's an overlap
self.double_bookings.append((overlap_start, overlap_end))
# If no triple booking, add the event to single bookings
self.single_bookings.append((start, end))
return True2779. Maximum Beauty of an Array After Applying Operation
def maximumBeauty(self, nums: list[int], k: int) -> int:
# Extend the range for each element in nums
events = []
for num in nums:
events.append((num - k, 1)) # Start of range
events.append((num + k + 1, -1)) # End of range (exclusive)
# Sort events by value, and in case of tie, by type of event
events.sort()
# Use a sweep line approach to calculate the maximum overlap
max_beauty = 0
current_count = 0
for value, effect in events:
current_count += effect
max_beauty = max(max_beauty, current_count)
return max_beauty57. Insert Interval
这道题很麻烦 感觉用了最笨的方法
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals:
return [newInterval]
mem = {newInterval[0]: 1}
mem[newInterval[1]] = mem.get(newInterval[1], 0) - 1
count = 0
ind = max(bisect_right([inte[0] for inte in intervals], newInterval[0]) - 1, 0)
if intervals[ind][1] < newInterval[0]:
ind += 1
res = intervals[:ind]
start = False
same = set()
while ind < len(intervals) and intervals[ind][0] <= newInterval[1]:
if intervals[ind][0] == intervals[ind][1]:
same.add(ind)
mem[intervals[ind][0]] = mem.get(intervals[ind][0], 0) + 1
mem[intervals[ind][1]] = mem.get(intervals[ind][1], 0) - 1
ind += 1
for inde, c in sorted(mem.items()):
count += c
if start and count == 0:
res[-1].append(inde)
start = False
elif not start:
res.append([inde])
# print(count)
if count == 0:
res[-1].append(inde)
start = True
# print(res, start)
return res + intervals[ind:]
太离谱了 有几个testcase嗯是不知道怎么错的
1353. Maximum Number of Events That Can Be Attended
def maxEvents(self, events: List[List[int]]) -> int:
event_que = []
res = 0
events = sorted(events, key = lambda x: x[0])
event_ind = 0
day = 0
while event_ind < len(events) or event_que:
if not event_que:
day = events[event_ind][0]
while event_ind < len(events) and day == events[event_ind][0]:
heappush(event_que, events[event_ind][1])
event_ind += 1
while event_que and event_que[0] < day:
heappop(event_que)
if event_que:
heappop(event_que)
res += 1
day += 1
return res