My brain rejects the possibility of an O(N^2) solution without even thinking about it. The only solution I can rationalize for this problem is the segment tree one. But looking at what you did, it seems super elegant and original.
Great intuition and explanation! Just one comment - the name 'non_overlapping' for the array is little misleading as it may contain overlapping intervals as we are adding all intervals to it. I would name it as 'bookings" or 'all_intervals'.
Another approach: We could also just maintain a sortedlist(). And when booking we can add to the list the tart val and a 1 as a tuple, then we can add a tuple of the end val and -1. Then we just need to iterate over the list and add those 1s and -1s we added, if their sum becomes ==3, there is a triple booking so we remove the element and return False. 🙂
Don’t treat it as a failure. Treat it as a learning experience! Learn, deeply understand, repeat it in your head and you will have a new tool for the future!
Hi Navdeep, what's up? I was expecting the solution of today's problem 432, All O' one Data Structure, it's fine if you are not in the state of making that video, thanks for being a really good mentor ❤
In that case yesterday's my cal 1 should have been this: ``` class MyCalendar: def __init__(self): self.o = [] def book(self, start: int, end: int) -> bool: for s, e in self.o: if end > s and e > start: return False self.o.append((start, end)) return True ``` Disclaimer it is accepted with 40% beating others
The focus of the problem is to create a class that can handle the addition of new intervals at any point in time. The intervals are not given in a sorted list. So you will need to sort the list each time, getting a worse time complexity
correct me if i’m wrong but can’t we just use calendar 1 solution but have two trees? you have a tree with all the double overlapped areas (not bookings, but areas), so you check every booking through that tree first. if there’s no overlap, you add to the main tree where all the bookings were stored like calendar 1. as you’re going through, you detect any overlaps. if there is a new double overlap, then you have to add that to the double overlap tree.
@@MrACrazyHobo yes it's a brute force O(n^2) complexity for the code given in the vid. so if u used binary search/bisect/insort to solve calendar 1 you probably have O(nlogn) (and you can appropriate it here if you wish to). but if you somehow performed sorting on every function call (which u 100% don't have to) then it would grow to be O(n^2logn).
can someone tell me why this doesnt work please thank you bool: if not self.root: self.root = TreeNode([start, end]) return True curr = self.root while curr: if start >= curr.range[1]: if not curr.right: curr.right = TreeNode([start, end]) break curr = curr.right elif end l and start < r: return False res = True if start < curr.range[0]: res = res & self.book(start, curr.range[0]) if end > curr.range[1]: res = res & self.book(curr.range[1], end) if res: curr.over.append([max(start, curr.range[0]), min(end, curr.range[1])]) return res return True
My brain rejects the possibility of an O(N^2) solution without even thinking about it. The only solution I can rationalize for this problem is the segment tree one. But looking at what you did, it seems super elegant and original.
Keep up the good work, neet!
🎉
Great intuition and explanation! Just one comment - the name 'non_overlapping' for the array is little misleading as it may contain overlapping intervals as we are adding all intervals to it. I would name it as 'bookings" or 'all_intervals'.
Another approach:
We could also just maintain a sortedlist(). And when booking we can add to the list the tart val and a 1 as a tuple, then we can add a tuple of the end val and -1. Then we just need to iterate over the list and add those 1s and -1s we added, if their sum becomes ==3, there is a triple booking so we remove the element and return False. 🙂
Interesting, could you share your code?
@@33galactus
def __init__(self):
self.db=SortedList()
def book(self, start: int, end: int) -> bool:
s,e=(start,1),(end,-1)
self.db.add(s)
self.db.add(e)
total=0
for _,c in self.db:
total+=c
if total==3:
self.db.remove(s)
self.db.remove(e)
return False
return True
This is O(n) per insertion. assuming insertion of n times. you have a triangle. A triangle is n*2/2 so O(n^2).
Damn, I was truly overthinking this one. Thank you so much for your clear and straightforward explanation!
no way i could think of it even after solving yesterday's problem. meh :(
Don’t treat it as a failure. Treat it as a learning experience! Learn, deeply understand, repeat it in your head and you will have a new tool for the future!
Similar to my calendar I, you could solve this with two BSTs with a time complexity of O(logn)
Use Line sweep algorithm and solve it can solve in O(n)
saviour and amazing explanation
Another great explanation. Thank you
love your videos buddy, thankyou for your explanation
Hi Navdeep, what's up? I was expecting the solution of today's problem 432, All O' one Data Structure, it's fine if you are not in the state of making that video, thanks for being a really good mentor ❤
So, if I'm understanding if we are looking for a quadruple overlapping we just add another list?
In that case yesterday's my cal 1 should have been this:
```
class MyCalendar:
def __init__(self):
self.o = []
def book(self, start: int, end: int) -> bool:
for s, e in self.o:
if end > s and e > start:
return False
self.o.append((start, end))
return True
```
Disclaimer it is accepted with 40% beating others
This is O(n) for each insertion, where as the BST from mycal 1 was O(logn) per insertion
Thank you
what if there were k No of bookings allowed , how would we solve it?
Line Sweep algorithm is easier and more intuitive.
The focus of the problem is to create a class that can handle the addition of new intervals at any point in time. The intervals are not given in a sorted list. So you will need to sort the list each time, getting a worse time complexity
@@alexandrunechifor1878 This is what treeMap(ordered set in c++) is for .
correct me if i’m wrong but can’t we just use calendar 1 solution but have two trees? you have a tree with all the double overlapped areas (not bookings, but areas), so you check every booking through that tree first. if there’s no overlap, you add to the main tree where all the bookings were stored like calendar 1. as you’re going through, you detect any overlaps. if there is a new double overlap, then you have to add that to the double overlap tree.
How would you build a binary tree for overlapping intervals (which interval is less if they overlap)?
how i'm not being able to build such logic,
Im yours big fan
This was crazy. No way one can solve in real interview without having seen.
Somewhat unfortunate variable naming. Apparently self.non_overlapping may contain overlapping intervals and self.overlapping cannot.
Is it not O(N^2) why is everyone saying O(N)
It's O(N) per input i.e. time complexity of the 'book' function. The overall time complexity for N inputs is O(N^2).
Segment tree please ❤
I'm struggling to understand how my calendar ii is O(n) time complexity, but my calendar i is O(nlogn) time complexity
My cal 1 was O(logn) because it used a BST
its O(n) per operation for this problem, sounds like you performed a sorting every operation for calendar i
@@ozempickin Ah it's O(n) per operation, so then it's O(n^2) total time complexity?
@@MrACrazyHobo yes it's a brute force O(n^2) complexity for the code given in the vid. so if u used binary search/bisect/insort to solve calendar 1 you probably have O(nlogn) (and you can appropriate it here if you wish to). but if you somehow performed sorting on every function call (which u 100% don't have to) then it would grow to be O(n^2logn).
Hi bro, get up and update today's video.🤣
lmao, here for the same thing
This is not O(N) time complexity, you're iterating over the list on every call. It's O(N^2) complexity
It's O(2*n)
same doubt...
@@iriteshit’s O(N^2) if N is the number of total calls to the function. It is O(N) if N is the number of booked events.
can someone tell me why this doesnt work please thank you bool:
if not self.root:
self.root = TreeNode([start, end])
return True
curr = self.root
while curr:
if start >= curr.range[1]:
if not curr.right:
curr.right = TreeNode([start, end])
break
curr = curr.right
elif end l and start < r:
return False
res = True
if start < curr.range[0]:
res = res & self.book(start, curr.range[0])
if end > curr.range[1]:
res = res & self.book(curr.range[1], end)
if res:
curr.over.append([max(start, curr.range[0]), min(end, curr.range[1])])
return res
return True