Student
more
Question states to create a class called my calendar III which has a function which adds bookings to the calendar. When you add a booking with a start and end time, which are integers, you have to return the max number of intersections between the bookings for the calender.
Ex. Let’s say the bookings are as follows:
The first booking would return 1, because the max number of intersections would be itself intersected. The second booking would return 2, because 10, 20 intersects with 15, 30 The third booking would return 2, because 10, 20 x 15, 30 and nothing intersects with 40, 50 The fourth booking would return 3, because 3, 18 x 10, 20 x 15, 30 (x = intersects)
00000000011111111111000000000000000000000000000000
00000000000000111111111111111111110000000000000000
00000000000000000000000000000000000000011111111111
00111111111111111100000000000000000000000000000000
Doing a linear scan from left to right across each column, you can tell the three is the maximum intersection because the end of any list comes before the 3rd beginning. Indeed, at 15 you can tell that all three ranges are valid, but the only information you need are the starts and ends.
declare class
class construction
create hashmap/dictionary
function book which accepts start and end
use class dictionary to record start times and end times
start times will have value 1 for each whereas end times will have value -1
go thru sorted dictionary (left to right)
save a total running sum of the start times and end times
save a maximum variable for the maximum intersections
return the maximum variable
This is what the code would look like.
class MyCalendarThree:
def __init__(self):
self.d = defaultdict(int)
def book(self, start: int, end: int) -> int:
self.d[start] += 1
self.d[end] -= 1
total = 0
maximum = 0
for key in sorted(self.d.keys()):
total += self.d[key]
maximum = max(total, maximum)
return maximum
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(start,end)
Runtime: 4563 ms, faster than 5.23% of Python3 online submissions for My Calendar III.
Memory Usage: 14.3 MB, less than 92.31% of Python3 online submissions for My Calendar III.
Let’s say we have n bookings. This means we have 2*n keys in the dictionary assuming worst case scenario where each key is unique. This means that we have to sort which best case scenario for sorting is O(nlogn) which means the function has a complexity of \(\Theta(4n^2log(2n))\) This means the big O value is \(\Omicron(n^2logn)\), because constants don’t matter after extremely large n \(4n^2log(2n) \le n^2logn\)
Faster solutions use SortedDict, which adds the key in its sorted position, rather than sorts the whole key list everytime book is called. This would be the optimal solution.
Break a Palindrome Question states that given a palindrome, create the next lexicographical string that turns it no longer into a palindrome. Ex. abccba aaccba To solve this, you convert the next letter which is not an ‘a’ to an ‘a’ so that it becomes the next string. This will always be the next lexicographical string. For the case where all the letters are ‘a’ aaaaaaaa aaaaaaab You want the...
read more
Two Sum Attempt to recall: Question is “Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.” Intersection of Two Arrays vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> ans; vector<int>::iterator it; for(int i = 0; i < nums1.size(); i++){ it = find(nums2.begin(),nums2.end(),nums1[i]); if( it != nums2.end() ){ ans.push_back(nums1[i]); *it = -1; } } return ans; } vector<int>...
read more