My Calendar 1(I) Leetcode | Complete Explanation | Microsoft Coding Problem

0:00 - Problem Explanation
6:00 - Brute Force Approach
10:20 - Building Intuition for Optimized Approach
13:40 - Optimized Approach
18:56 - Code

Use code rite2riddhi for 10% discount on all courses on Unacademy

Use code RIDDHIDUTTA for 10% discount on all courses on GFG

Tags
DSA
Coding Interview
Leetcode
Leetcode Medium
TreeSet
JAVA
riddhi dutta

[riteriddhi]

Have improved Video quality. And audio bhi. Subscribe kar dena :)

[iamnoob]

WOW Time just passed i just watched it continuous till end. Thanks Riddhi

[VegerotN]

For cpp should we use ordered_map or ordered_set?

[utkarshagarwal]

Bhaiya Amazon ki nyi policy aap follow kar rhe ?
YouTube leave karne wali ?

[alphadrones]

template<typename Key, typename Value>
using MapIterator = typename std::map<Key, Value>::const_iterator;

template<typename Key, typename Value>
Key floorKey(const std::map<Key, Value>& input, const Key& key){
/*
map::upper_bound(>):
Returns an iterator pointing to the first element in the container
whose key is considered to go after k.

If k is larger than any key in the map, then it returns map::end
*/
MapIterator<Key, Value> it = input.upper_bound(key);
if (it != input.begin()) {
return (--it)->first;
} else {
//assume Key is int
return -1;
}
}

template<typename Key, typename Value>
Key ceilingKey(const std::map<Key, Value>& input, const Key& key){
/*
map::lower_bound(>=):
Returns an iterator pointing to the first element
in the container whose key is not considered to go before k
(i.e., either it is equivalent or goes after).
*/
MapIterator<Key, Value> it = input.lower_bound(key);
if (it != input.end()) {
return it->first;
} else {
//assume Key is int
return -1;
}
}

class MyCalendar {
private:
map<int, int> bookings;
public:
MyCalendar() {

}

bool book(int start, int end) {

int prevBooking = floorKey(bookings, start);
int nextBooking = ceilingKey(bookings, start);

if((prevBooking == -1 || bookings[prevBooking] <= start) &&
(nextBooking == -1 || end <= nextBooking)){
bookings[start] = end;
return true;
}

return false;

}
};
c++ solution

[yashkumbhoje]

Hello sir i have stammering problem does it affect my software engineering career 😭

[girikgarg]

What if I am using C++ language to solve this question?

[hey.............]

class MyCalendar {
TreeMap<Integer, Integer> tm;
public MyCalendar() {
tm = new TreeMap<>();
}

public boolean book(int start, int end) {
Integer leftBooking = tm.floorKey(start);
Integer rightBooking = tm.ceilingKey(start);
if(leftBooking != null && tm.get(leftBooking) > start) {
return false;
}
if(rightBooking != null && rightBooking < end) {
return false;
}
tm.put(start, end);
return true;
}
}