Who are you? You have all these excellent videos, but I am interested in learning why you aren’t working as a software engineer. Could you make videos about yourself? I’m sure other people are curious as well
You can you a heap for this to run in linear time... Just start adding it based on the end time... So you'll only have to check the top most value... If it's greater just add it to the. Heap.. else pop it. And push the new value. Return true or false based on this?
@@nedimaylamaz5604 There are several sorting algorithms. The most efficient ones like Merge Sort has n*log(n) time complexity. Built-in sorting functions most likely use these algorithms and thus have n*log(n) time complexity
wouldn't we be able to keep track of the total time spent in meetings and the earliest and latest starting and ending times, then compare to see if the total time is less than the latest-earliest? This would be an O(n) solution, i'm unsure if there's some edge case that i'm missing or something
It made more sense for me to store the last meeting's end time, and making that the next possible start time. This is how I solved it: class Solution: def canAttendMeetings(self, intervals: List[Interval]) -> bool: intervals.sort(key=lambda i: i.start) start = 0 for i in intervals: if i.start < start: return False else: start = i.end return True
I ran this linear O(n) approach and it worked both in neetcode and lintcode int n=intervals.size(); for(int i=0;i intervals[i+1].start && intervals[i].start
Can you not make a linear solution: public boolean canAttendMeetings(List intervals) { if(intervals.size() < 2) { return true; } for(int i = 1; i < intervals.size(); i++) { int maxStart = Math.max(intervals.get(i - 1).start, intervals.get(i).start); int minEnd = Math.min(intervals.get(i - 1).end, intervals.get(i).end); if(maxStart < minEnd) { return false; } } return true; }
won't this linear approach work? def canAttendMeetings(intervals): start = min(intervals, key=lambda x:x[0])[0] end = max(intervals, key=lambda x:x[1])[1] expected_t = sum(x[1]-x[0] for x in intervals) made_t = end - start return made_t >= expected_t
Thanks for the LC premium workaround!
This guy saving us all with the lifehack!
Glad I found this gem of a channel.
You are a hero we do not deserve, but desperately need.
Teaching us AND saving us money...double whammy!
You explain it so lucidly.. makes me kick myself that I couldnt think of that!! haha.. thank you so much for inspiring us to improve
Thanks man, just wanted to make sure my solution was good, and it was the same as yours. Liked!
Who are you? You have all these excellent videos, but I am interested in learning why you aren’t working as a software engineer. Could you make videos about yourself? I’m sure other people are curious as well
I hope to answer all of the above questions in the very near future 🙂
@@NeetCode i believe you can have your answer now)
@@NeetCode Man you did it. Really inspiring journey. So happy for you!!
"I don't know how they can get away with doing that" - proceeds to do it himself as well 😂
I actually got this question during my interview with Meta!
God I hope this is what I get
@@emachine003 Prob not unfortunately, the times have changed
@@danieldsouza2657 yeah theyre gonna be giving hards and meds only
this is too easy for Meta, no?
Maaan you are amazing!!!
thanks for the lintcode 🔥
You can you a heap for this to run in linear time... Just start adding it based on the end time... So you'll only have to check the top most value... If it's greater just add it to the. Heap.. else pop it. And push the new value.
Return true or false based on this?
Popping and adding to a heap takes log(n) time, worst case we need to add everything to the heap (ie: there are no conflicts) so that is n*log(n)
Can we do by sorting by end time? Logic: Arrabge them by end and then see if anyone's end time is overlapping with the next one's starting time?
Great video! Why is it nlog(n) ?
Sorting is n log(n)
@@JasonKim1 How do we measure the sorting is n log(n)
@@nedimaylamaz5604 There are several sorting algorithms. The most efficient ones like Merge Sort has n*log(n) time complexity. Built-in sorting functions most likely use these algorithms and thus have n*log(n) time complexity
wouldn't we be able to keep track of the total time spent in meetings and the earliest and latest starting and ending times, then compare to see if the total time is less than the latest-earliest? This would be an O(n) solution, i'm unsure if there's some edge case that i'm missing or something
Won't work for examples with large gaps between meetings ie. [1,5] [2, 5] [100, 101]
Is there a way to do this without sorting?
Can you please make video on leetcode problem Predict the winner.
Neetcode & Lintcode FTW
first of, your explanations are amazing! and q, shouldn't it be, i1.end >= i2.start ?
Late response but in this problem if the end time and start time are equal it doesn't count as a conflict
Do more of this!!!!
It made more sense for me to store the last meeting's end time, and making that the next possible start time.
This is how I solved it:
class Solution:
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
intervals.sort(key=lambda i: i.start)
start = 0
for i in intervals:
if i.start < start:
return False
else:
start = i.end
return True
what if we sort the intervals by ending times? will that work?
I tried it and it works
en.wikipedia.org/wiki/Interval_scheduling#:~:text=The%20greedy%20algorithm%20can%20be%20executed%20in%20time%20O(n%20log%20n)%2C%20where%20n%20is%20the%20number%20of%20tasks%2C%20using%20a%20preprocessing%20step%20in%20which%20the%20tasks%20are%20sorted%20by%20their%20finishing%20times.
I ran this code you had in your video, but it did not pass test case [[7,10],[2,4]]
if you sorted the intervals first it should work
Wouldn't it be more efficient to build a tree based on start times. The solution would only be log n time complexity.
I ran this linear O(n) approach and it worked both in neetcode and lintcode
int n=intervals.size();
for(int i=0;i intervals[i+1].start && intervals[i].start
The description for this question on leetcode is terrible. The examples don't help at all.
i dont think this would pass by an interviewer, as you should probably sort without using a built in library.
New 21 please
Can you not make a linear solution:
public boolean canAttendMeetings(List intervals) {
if(intervals.size() < 2) {
return true;
}
for(int i = 1; i < intervals.size(); i++) {
int maxStart = Math.max(intervals.get(i - 1).start, intervals.get(i).start);
int minEnd = Math.min(intervals.get(i - 1).end, intervals.get(i).end);
if(maxStart < minEnd) {
return false;
}
}
return true;
}
Make meetingr room 2 bro
ruclips.net/video/FdzJmTCVyJU/видео.html
oh that's how you sort a list of objects
ikr - so useful and clutch
won't this linear approach work?
def canAttendMeetings(intervals):
start = min(intervals, key=lambda x:x[0])[0]
end = max(intervals, key=lambda x:x[1])[1]
expected_t = sum(x[1]-x[0] for x in intervals)
made_t = end - start
return made_t >= expected_t
It's pronounced "tuh pl" as in quintuple.