· 4 years ago · Apr 19, 2021, 05:16 PM
1https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string/
21)
3class Solution:
4 def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
5 hash_ = {}
6 for item in knowledge:
7 hash_[item[0]] = item[1]
8 output = ""
9 i = 0
10 n = len(s)
11 while i < n:
12 if s[i] != "(":
13 output += s[i]
14 else:
15 j = i+1
16 while s[j] != ")" and j < n:
17 j += 1
18 key = s[i+1:j]
19 if key in hash_:
20 output += hash_[key]
21 else:
22 output += "?"
23 i = j
24 i += 1
25
26 return output
272)
28https://leetcode.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation/
29
30Example 1:
31
32Input: n = 2
33Output: 1
34Explanation: perm = [0,1] initially.
35After the 1st operation, perm = [0,1]
36So it takes only 1 operation.
37Example 2:
38
39Input: n = 4
40Output: 2
41Explanation: perm = [0,1,2,3] initially.
42After the 1st operation, perm = [0,2,1,3]
43After the 2nd operation, perm = [0,1,2,3]
44So it takes only 2 operations.
45Example 3:
46
47Input: n = 6
48Output: 4
49
50class Solution:
51 def compare_array(self, first, second):
52 if len(first) != len(second):
53 return False
54 for index in range(len(first)):
55 if first[index] != second[index]:
56 return False
57 return True
58
59 def reinitializePermutation(self, n: int) -> int:
60 perm = [i for i in range(n)]
61 orig_perm = copy.deepcopy(perm)
62 i = 0
63 j = 0
64 while j < n:
65 i = 0
66 j += 1
67 arr = [0 for i in range(n)]
68 for i in range(n):
69 if i %2 == 0:
70 arr[i] = perm[int(i / 2)]
71 elif i %2 == 1:
72 arr[i] = perm[int(n / 2 + ((i - 1) / 2))]
73 i += 1
74 #print(arr)
75 perm = arr
76 if self.compare_array(arr, orig_perm):
77 return j
78 return j
79
803)https://leetcode.com/problems/number-of-different-integers-in-a-string/
81
82class Solution:
83 def lstrip(self, item):
84 i = 0
85 l = len(item)
86 while i < l:
87 if item[i] == '0':
88 i += 1
89 else:
90 return item[i:l]
91 if i == l:
92 return ""
93 else:
94 return item[i:l]
95
96 def numDifferentIntegers(self, word: str) -> int:
97 if not word:
98 return 0
99 temp = ""
100 for char in word:
101 if char.isdigit():
102 temp += char
103 else:
104 temp += " "
105 print(temp)
106 temp = temp.split(" ")
107 print(temp)
108 set_p = dict()
109 for item in temp:
110 if item != "":
111 set_p[self.lstrip(item)] = 1
112 print(set_p)
113 return len(set_p)
114
115
1164) https://leetcode.com/problems/k-closest-points-to-origin/
117
118class Solution:
119 def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
120 heap = []
121 for point in points:
122 dist = point[0]*point[0] + point[1]*point[1]
123 heapq.heappush(heap, (-dist, point))
124
125 while len(heap) > k:
126 heapq.heappop(heap)
127 return [value for key, value in heap]
128
1295) https://leetcode.com/problems/last-stone-weight/
130class Solution:
131 def lastStoneWeight(self, stones: List[int]) -> int:
132 #use max heap
133 heap = []
134 for stone in stones:
135 heapq.heappush(heap,-stone)
136 while True:
137 light = heapq.heappop(heap)
138 if len(heap) == 0:
139 return -light
140 heavy = heapq.heappop(heap)
141 if light == heavy:
142 if len(heap) == 0:
143 return 0
144 elif light != heavy:
145 heavy = -light - -heavy
146 heapq.heappush(heap, -heavy)
147
1486) https://leetcode.com/problems/number-of-orders-in-the-backlog/
149class Solution:
150 def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
151 buy_heap = [] #max
152 sell_heap = [] #min heap
153 for price, amount, order in orders:
154 if order == 0: #sell
155 heapq.heappush(buy_heap, [-price, amount])
156 else:
157 heapq.heappush(sell_heap, [price, amount])
158
159 while buy_heap and sell_heap and sell_heap[0][0] <= -buy_heap[0][0]:
160 amount = min(buy_heap[0][1], sell_heap[0][1])
161 sell_heap[0][1] -= amount
162 buy_heap[0][1] -= amount
163 if sell_heap[0][1] == 0:
164 heapq.heappop(sell_heap)
165 if buy_heap[0][1] == 0:
166 heapq.heappop(buy_heap)
167
168 ans = 0
169 for price, amount in buy_heap:
170 ans += amount
171 for price, amount2 in sell_heap:
172 ans += amount2
173
174 return ans % (10**9 + 7)
175
1767) https://leetcode.com/problems/reveal-cards-in-increasing-order/
177import collections
178class Solution:
179 def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
180 index = collections.deque(range(0, len(deck)))
181 ans = [None] * len(deck)
182 deck = sorted(deck)
183 for i in range(len(deck)):
184 ans[index.popleft()] = deck[i]
185 if index:
186 index.append(index.popleft())
187 return ans
188
189https://leetcode.com/problems/first-missing-positive/
190class Solution:
191 def firstMissingPositive(self, nums: List[int]) -> int:
192 if not nums:
193 return 1
194 if 1 not in nums:
195 return 1
196 if nums==[1]:
197 return 2
198 #check for violations
199 n = len(nums)
200 for index, num in enumerate(nums):
201 if num <= 0 or num > n:
202 nums[index] = 1
203
204 for index, num in enumerate(nums):
205 a = abs(nums[index])
206 if a < n:
207 nums[a] = - abs(nums[a])
208 elif a == n:
209 nums[0] = - abs(nums[0])
210
211 for i in range(1, n):
212 if nums[i] > 0:
213 return i
214
215 if nums[0] > 0:
216 return n
217
218 return n+1
2198) https://leetcode.com/problems/largest-unique-number/submissions/
220class Solution:
221 def largestUniqueNumber(self, A: List[int]) -> int:
222 hash_table = {}
223 for item in A:
224 if item not in hash_table:
225 hash_table[item] = 1
226 else:
227 hash_table[item] += 1
228
229 output = -1
230 for key, value in hash_table.items():
231 if value == 1:
232 output = max(output, key)
233
234 return output
235
2369)https://leetcode.com/contest/weekly-contest-233/problems/maximum-value-at-a-given-index-in-a-bounded-array/
237class Solution:
238 def maxValue(self, n: int, index: int, maxSum: int) -> int:
239 left = index
240 right = index
241 res = 1 #initially it's 1
242 sum_ = n
243 while sum_ + right - left + 1 <= maxSum:
244 sum_ += (right - left +1)
245 if left == 0:
246 left = 0
247 else:
248 left = left - 1
249
250 if right == n-1:
251 right = n-1
252 else:
253 right = right + 1
254 res += 1
255 if left == 0 and right == n-1:
256 steps = (maxSum - sum_)//n
257 sum_ += (maxSum - sum_)
258 res += steps
259 return res
260
26110) https://leetcode.com/problems/top-k-frequent-elements/
262
263class Solution:
264 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
265 hash_table = collections.defaultdict(list)
266 for key, value in Counter(nums).items():
267 hash_table[value].append(key)
268 output = []
269 _k = k
270 for freq in reversed(range(len(nums) + 1)):
271 if len(output) >= k:
272 return output
273 if freq in hash_table:
274 output.extend(hash_table[freq])
275 return output
27611) https://leetcode.com/problems/maximum-score-from-removing-stones/
277class Solution:
278 def maximumScore(self, a: int, b: int, c: int) -> int:
279 heap = []
280 heapq.heappush(heap, -a)
281 heapq.heappush(heap, -b)
282 heapq.heappush(heap, -c)
283 output = 0
284 while len(heap) > 1:
285 first_top = - heapq.heappop(heap)
286 second_top = - heapq.heappop(heap)
287 output += 1
288
289 first_top -=1
290 second_top -=1
291 if first_top > 0:
292 heapq.heappush(heap, -first_top)
293 if second_top > 0:
294 heapq.heappush(heap, -second_top)
295
296 return output
297
29812) https://leetcode.com/problems/kth-largest-element-in-an-array/
299o(n) average time o(n2) worst time
300class Solution:
301 def swap(self, nums, from_, to):
302 temp = nums[from_]
303 nums[from_] = nums[to]
304 nums[to] = temp
305
306 def partition(self, nums, low, high):
307 pivot = nums[high]
308 l = low
309 for i in range(low, high):
310 if nums[i] <= pivot:
311 self.swap(nums, i, l)
312 l += 1
313 self.swap(nums, l, high)
314 print("Partitiion at {0}".format(l), nums)
315 return l
316
317 def util(self,nums, low, high, k):
318 if k > 0 and k <= high - low + 1:
319 pivot = self.partition(nums, low, high)
320 if k - 1 > pivot - low:
321 return self.util(nums, pivot + 1, high, k - 1 - pivot + low)
322 elif pivot - low > k -1:
323 return self.util(nums,low, pivot -1 , k)
324 else:
325 return nums[pivot]
326
327 def findKthLargest(self, nums: List[int], k: int) -> int:
328 return self.util(nums, 0, len(nums)-1, len(nums)-k+1)
329
330
331O(k + (n-k) log k), space: O(k)
332class Solution:
333 def findKthLargest(self, nums: List[int], k: int) -> int:
334 heap = nums[:k]
335 heapq.heapify(heap)
336 for num in nums[k:]:
337 if num > heap[0]:
338 heapq.heapreplace(heap, num)
339
340 return heap[0]
341
342O(nlogk)
343class Solution:
344 def findKthLargest(self, nums: List[int], k: int) -> int:
345 heap = nums[:]
346 heapq.heapify(heap)
347 while len(heap) > k:
348 heapq.heappop(heap)
349 return heap[0]
350
351# O(nlgn) time
352def findKthLargest1(self, nums, k):
353 return sorted(nums, reverse=True)[k-1]
354
355# O(n+(n-k)logn) time, min-heap
356def findKthLargest4(self, nums, k):
357 heap = []
358 for num in nums:
359 heapq.heappush(heap, num)
360 for _ in xrange(len(nums)-k):
361 heapq.heappop(heap)
362 return heapq.heappop(heap)
363
364
365
36613)https://leetcode.com/problems/move-zeroes/
367
368class Solution:
369 def moveZeroes(self, nums: List[int]) -> None:
370 """
371 Do not return anything, modify nums in-place instead.
372 """
373 def swap(nums, from_, to):
374 nums[from_], nums[to] = nums[to], nums[from_]
375 zero = 0
376 for i in range(len(nums)):
377 if nums[i] != 0:
378 swap(nums, i, zero)
379 zero += 1
380 return nums
381
38214) https://leetcode.com/problems/sort-colors/submissions/
383class Solution:
384 def sortColors(self, nums: List[int]) -> None:
385 """
386 Do not return anything, modify nums in-place instead.
387 """
388 def swap(nums, from_, to):
389 nums[from_], nums[to] = nums[to], nums[from_]
390
391 low = 0
392 mid = 0
393 high = len(nums) -1
394 while mid <= high:
395 if nums[mid] == 0:
396 swap(nums, low, mid)
397 low += 1
398 mid += 1
399 elif nums[mid] == 1:
400 mid += 1
401 elif nums[mid] == 2:
402 swap(nums, mid, high)
403 high -=1
404 return nums
405
40615) https://leetcode.com/problems/shortest-path-in-a-hidden-grid/submissions/
407
408Input: grid = [[1,2],[-1,0]]
409Output: 2
410Explanation: One possible interaction is described below:
411The robot is initially standing on cell (1, 0), denoted by the -1.
412- master.canMove('U') returns true.
413- master.canMove('D') returns false.
414- master.canMove('L') returns false.
415- master.canMove('R') returns false.
416- master.move('U') moves the robot to the cell (0, 0).
417- master.isTarget() returns false.
418- master.canMove('U') returns false.
419- master.canMove('D') returns true.
420- master.canMove('L') returns false.
421- master.canMove('R') returns true.
422- master.move('R') moves the robot to the cell (0, 1).
423- master.isTarget() returns true.
424We now know that the target is the cell (0, 1), and the shortest path to the target cell is 2.
425
426# """
427# This is GridMaster's API interface.
428# You should not implement it, or speculate about its implementation
429# """
430#class GridMaster(object):
431# def canMove(self, direction: str) -> bool:
432#
433#
434# def move(self, direction: str) -> bool:
435#
436#
437# def isTarget(self) -> None:
438#
439#
440
441class Solution(object):
442 def findShortestPath(self, master: 'GridMaster') -> int:
443 pos = {"U":(-1,0), "D":(1,0), "L":(0,-1), "R":(0,1)}
444 anti = {"U":"D", "D":"U", "L":"R", "R":"L"}
445 isvalid = {}
446 isvalid [(0,0)] = master.isTarget()
447 def dfs(i, j):
448 for dir in pos:
449 x, y = pos[dir][0] + i, pos[dir][1] + j
450 if master.canMove(dir) and (x,y) not in isvalid:
451 master.move(dir)
452 isvalid[(x,y)] = master.isTarget()
453 dfs(x,y)
454 master.move(anti[dir])
455 dfs(0,0)
456 qu = collections.deque([(0,0,0)]) #x, y, step
457 seen = set()
458 while len(qu) > 0:
459 x, y, step = qu.popleft()
460 if isvalid[(x,y)] == True:
461 return step
462 for i, j in [[x+1, y], [x-1,y],[x,y-1], [x, y+1]]:
463 if (i,j) in isvalid and (i,j) not in seen:
464 seen.add((i,j))
465 qu.append((i,j, step+1))
466 return -1
467
46816) https://leetcode.com/problems/longest-valid-parentheses/submissions/
469
470Input: s = "(()"
471Output: 2
472Explanation: The longest valid parentheses substring is "()".
473Example 2:
474
475Input: s = ")()())"
476Output: 4
477Explanation: The longest valid parentheses substring is "()()".
478Example 3:
479
480Input: s = ""
481Output: 0
482
483class Solution:
484 def longestValidParentheses(self, s: str) -> int:
485 stack = [-1]
486 maxlen = 0
487 if not s or s == "" or len(s) < 2:
488 return 0
489 for i in range(len(s)):
490 #print(stack)
491 if s[i] == "(":
492 stack.append(i)
493 else:
494 stack.pop()
495 if len(stack) != 0:
496 maxlen = max(maxlen, i - stack[-1])
497 else:
498 stack.append(i)
499 return maxlen
500
50117) https://leetcode.com/problems/design-circular-queue/
502class MyCircularQueue:
503
504 def __init__(self, k: int):
505 self.capacity = k
506 self.array = [None] * self.capacity
507 self.front = 0
508 self.size = 0
509
510 def enQueue(self, value: int) -> bool:
511 if self.isFull():
512 return False
513
514 avail = (self.front + self.size) % self.capacity
515 self.array[avail] = value
516 self.size += 1
517 return True
518
519 def deQueue(self) -> bool:
520 if self.isEmpty():
521 return False
522 self.array[self.front] = None
523 self.front = (self.front + 1) % self.capacity
524 self.size -= 1
525 #print(self.array)
526 return True
527
528 def Front(self) -> int:
529 if self.isEmpty():
530 return -1
531 return self.array[self.front]
532
533 def Rear(self) -> int:
534 if self.isEmpty():
535 return -1
536
537 rear = (self.front + self.size -1) % self.capacity
538 return self.array[rear]
539
540 def isEmpty(self) -> bool:
541 if self.size == 0:
542 return True
543 return False
544
545 def isFull(self) -> bool:
546 if self.size == self.capacity:
547 return True
548 return False
549
550from threading import Lock
551
552class MyCircularQueue:
553
554 def __init__(self, k: int):
555 """
556 Initialize your data structure here. Set the size of the queue to be k.
557 """
558 self.queue = [0]*k
559 self.headIndex = 0
560 self.count = 0
561 self.capacity = k
562 # the additional attribute to protect the access of our queue
563 self.queueLock = Lock()
564
565 def enQueue(self, value: int) -> bool:
566 """
567 Insert an element into the circular queue. Return true if the operation is successful.
568 """
569 # automatically acquire the lock when entering the block
570 with self.queueLock:
571 if self.count == self.capacity:
572 return False
573 self.queue[(self.headIndex + self.count) % self.capacity] = value
574 self.count += 1
575 # automatically release the lock when leaving the block
576 return True
577
578# Your MyCircularQueue object will be instantiated and called as such:
579# obj = MyCircularQueue(k)
580# param_1 = obj.enQueue(value)
581# param_2 = obj.deQueue()
582# param_3 = obj.Front()
583# param_4 = obj.Rear()
584# param_5 = obj.isEmpty()
585# param_6 = obj.isFull()
586
58718) https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
588
589class Solution:
590 def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
591 heap = []
592 N = len(matrix)
593 for r in range(min(N, k)):
594 heap.append((matrix[r][0], r, 0))
595 heapq.heapify(heap)
596 k-=1
597 while k > 0:
598 #print(heap)
599 val, r, c = heapq.heappop(heap)
600 if c + 1 <= N-1:
601 heapq.heappush(heap, (matrix[r][c+1], r, c+1))
602 k-=1
603
604 return heap[0][0]
605
60619( https://leetcode.com/problems/search-a-2d-matrix-ii/submissions/
607class Solution:
608 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
609 if not matrix:
610 return False
611 if len(matrix) == 0:
612 return False
613 rows = len(matrix)
614 cols = len(matrix[0])
615
616 i = 0
617 j = cols -1
618 while i < rows and j >= 0:
619 if matrix[i][j] == target:
620 return True
621 elif matrix[i][j] < target:
622 i += 1
623 else:
624 j -=1
625 return False
626
62720)https://leetcode.com/problems/maximum-average-pass-ratio
628
629Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
630Output: 0.78333
631Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.
632Example 2:
633
634Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
635Output: 0.53485
636
637O(M*logN + N), where M is extraStudents and N is number of classes.
638
639class Solution:
640 def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
641
642 n = len(classes)
643
644 impacts = [0]*n
645 minRatioIndex = 0
646
647 # calculate and store impacts for each class in form of tuples -> (-impactValue, passCount, totalCount)
648 for i in range(n):
649 passCount = classes[i][0]
650 totalCount = classes[i][1]
651
652 # calculate the impact for class i
653 currentRatio = passCount/totalCount
654 expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
655 impact = expectedRatioAfterUpdate - currentRatio
656
657 impacts[i] = (-impact, passCount, totalCount) # note the - sign for impact
658
659 heapq.heapify(impacts)
660
661 while(extraStudents > 0):
662 # pick the next class with greatest impact
663 _, passCount, totalCount = heapq.heappop(impacts)
664
665 # assign a student to the class
666 passCount+=1
667 totalCount+=1
668
669 # calculate the updated impact for current class
670 currentRatio = passCount/totalCount
671 expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
672 impact = expectedRatioAfterUpdate - currentRatio
673
674 # insert updated impact back into the heap
675 heapq.heappush(impacts, (-impact, passCount, totalCount))
676 extraStudents -= 1
677
678 result = 0
679
680 # for all the updated classes calculate the total passRatio
681 for _, passCount, totalCount in impacts:
682 result += passCount/totalCount
683
684 # return the average pass ratio
685 return result/n
686
68721)https://leetcode.com/problems/global-and-local-inversions/
688
689We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.
690
691The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].
692
693The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].
694
695Return true if and only if the number of global inversions is equal to the number of local inversions.
696
697Example 1:
698
699Input: A = [1,0,2]
700Output: true
701Explanation: There is 1 global inversion, and 1 local inversion.
702Example 2:
703
704Input: A = [1,2,0]
705Output: false
706Explanation: There are 2 global inversions, and 1 local inversion.
707
708class Solution:
709 def isIdealPermutation(self, A: List[int]) -> bool:
710 for i in range(len(A)):
711 if A[i] == i or A[i] == i+1 or A[i] == i-1:
712 continue
713 return False
714 return True
715
71622)https://leetcode.com/problems/top-k-frequent-words/submissions/
717
718O(nlogk)
719
720class Solution:
721 def topKFrequent(self, words: List[str], k: int) -> List[str]:
722 hash_words = Counter(words)
723 output = []
724 heap = []
725 for word, count in hash_words.items():
726 heap.append((-count, word))
727
728 heapq.heapify(heap)
729 output = []
730 while k:
731 output.append(heapq.heappop(heap)[1])
732 k-=1
733 return output
734O(NlogN)
735class Solution:
736 def topKFrequent(self, words: List[str], k: int) -> List[str]:
737 hash_words = Counter(words)
738 output = []
739 counter_dict = collections.defaultdict(list)
740 for word, wc in hash_words.items():
741 counter_dict[wc].append(word)
742 output = []
743 for i in range(len(words)-1, -1, -1):
744 #print(i)
745 if i in counter_dict:
746 #print(counter_dict)
747 for elem in sorted(counter_dict[i]):
748 if k == 0:
749 return output
750 output.append(elem)
751 k -=1
752
753 return output
754
755
75623_ https://leetcode.com/problems/minimum-operations-to-make-array-equal/solution/
757
758Input: n = 3
759Output: 2
760Explanation: arr = [1, 3, 5]
761First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
762In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].
763class Solution:
764 def minOperations(self, n: int) -> int:
765 array = [2*i + 1 for i in range(n)]
766 mid = int(sum(array)/n)
767 output = 0
768 for i in array:
769 if i < mid:
770 output += (mid - i)
771 return output
772
77324) https://leetcode.com/problems/repeated-dna-sequences/submissions/
774class Solution:
775 def findRepeatedDnaSequences(self, s: str) -> List[str]:
776 hash_table = {}
777 if len(s) < 10:
778 return []
779 output = set()
780 for i in range(len(s)):
781 cur_string = s[i:i+10]
782 if cur_string in hash_table:
783 output.add(cur_string)
784 else:
785 hash_table[cur_string] = 1
786 return list(output)
787
78825)https://leetcode.com/problems/minimum-genetic-mutation/
789
790class Solution:
791 def minMutation(self, start: str, end: str, bank: List[str]) -> int:
792 if end not in bank:
793 return -1
794 word_dict = collections.defaultdict(set)
795 for word in bank:
796 for i in range(len(word)):
797 perm = word[:i] + "*" + word[i+1:]
798 word_dict[perm].add(word)
799 #print(word_dict)
800 queue = [(start,0)]
801 output = 0
802 visited = {}
803 #print(word_dict)
804 while queue:
805 word, level = queue.pop()
806 if word not in visited:
807 visited[word] = True
808 for i in range(len(word)):
809 perm = word[:i] + "*" + word[i+1:]
810 if perm in word_dict and end in word_dict[perm]:
811 return level+1
812 for elem in word_dict[perm]:
813 queue.append((elem, level+1))
814 return -1
815
81626)https://leetcode.com/problems/merge-intervals/submissions/
817
818class Solution:
819 def merge(self, intervals: List[List[int]]) -> List[List[int]]:
820 output = []
821 for interval in sorted(intervals, key = lambda x: x[0]):
822 if len(output) < 1 or output[-1][-1] < interval[0]:
823 output.append(interval)
824 continue
825 output[-1][-1] = max(output[-1][-1], interval[1])
826 return output
827
82827)https://leetcode.com/problems/meeting-rooms-ii/submissions/
829
830class Solution:
831 def minMeetingRooms(self, intervals: List[List[int]]) -> int:
832 start = [i for i, j in intervals]
833 end = [j for i, j in intervals]
834 start = sorted(start)
835 end = sorted(end)
836 i = 0
837 j = 0
838 total = 0
839 min_rooms = float("-inf")
840 #print(start, end)
841 while i < len(start) and j < len(end):
842 if start[i] < end[j]:
843 i += 1
844 total += 1
845 else:
846 total -= 1
847 j +=1
848 min_rooms = max(total, min_rooms)
849 return min_rooms
85028) https://leetcode.com/problems/meeting-rooms/
851class Solution:
852 def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
853 if not intervals:
854 return True
855 intervals = sorted(intervals, key=lambda x: x[0])
856 for i in range(1, len(intervals)):
857 if intervals[i][0] < intervals[i-1][1]: #Start of second less than end of first
858 return False
859 return True
860
86129)https://leetcode.com/problems/employee-free-time/
862
863"""
864# Definition for an Interval.
865class Interval:
866 def __init__(self, start: int = None, end: int = None):
867 self.start = start
868 self.end = end
869"""
870Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
871Output: [[3,4]]
872Explanation: There are a total of three employees, and all common
873free time intervals would be [-inf, 1], [3, 4], [10, inf].
874We discard any intervals that contain inf as they aren't finite
875class Solution:
876 def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
877 if not schedule:
878 return []
879 #flatten it
880 intervals = []
881 for emp in schedule:
882 for interval in emp:
883 intervals.append(interval)
884 #intervals = [interval for interval in emp for emp in schedule]
885 output = []
886 for interval in sorted(intervals, key = lambda x: x.start):
887 if len(output) < 1 or output[-1].end < interval.start:
888 output.append(interval)
889 else:
890 output[-1].end = max(output[-1].end, interval.end)
891 return_out = []
892 for i in range(1, len(output)):
893 return_out.append(Interval(output[i-1].end, output[i].start))
894
895 return return_out
896
89730) https://leetcode.com/problems/interval-list-intersections/submissions/
898Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
899Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
900Example 2:
901
902Input: firstList = [[1,3],[5,9]], secondList = []
903Output: []
904Example 3:
905
906Input: firstList = [], secondList = [[4,8],[10,12]]
907Output: []
908Example 4:
909
910Input: firstList = [[1,7]], secondList = [[3,10]]
911Output: [[3,7]]
912class Solution:
913 def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
914 if not firstList:
915 return []
916 if not secondList:
917 return []
918 i = 0
919 j = 0
920 res = []
921 while i < len(firstList) and j < len(secondList):
922 if firstList[i][0] <= secondList[j][1] and firstList[i][1] >= secondList[j][0]:
923 res.append([max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])])
924 if firstList[i][1] < secondList[j][1]:
925 i += 1
926 else:
927 j += 1
928 return res
929
930