LeetCode Entry

729. My Calendar I

26.09.2024 medium 2024 kotlin rust

Insert non-intersection interval search

729. My Calendar I medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/747

Problem TLDR

Insert non-intersection interval #medium #binary_search

Intuition

The problem size of 1000 allows the n^2 algorithm to pass. However, we can optimise it by finding a place to insert into sorted list. The intervals are non-intersection by definition.

Approach

• there is a cool partition_point method exists

Complexity

• Time complexity: \(O(nlog(n))\) or n^2 for Kotlin’s solution

• Space complexity: \(O(n)\)

Code

class MyCalendar() : ArrayList<Pair<Int, Int>>() {
    fun book(start: Int, end: Int): Boolean =
        none { (s, e) -> start < e && end > s }
        .also { if (it) add(start to end) }
}

struct MyCalendar(Vec<(i32, i32)>);
impl MyCalendar {
    fn new() -> Self { Self(vec![]) }
    fn book(&mut self, start: i32, end: i32) -> bool {
        let less = self.0.partition_point(|&(s, e)| e <= start);
        let more = self.0.partition_point(|&(s, e)| s < end);
        less == more && { self.0.insert(more, (start, end)); true }
    }
}

class MyCalendar {
public:
    MyCalendar() {}
    vector<pair<int, int>> list;
    bool book(int start, int end) {
        auto less = partition_point(list.begin(), list.end(),
            [start](const auto& b){ return b.second <= start; });
        auto more = partition_point(list.begin(), list.end(),
            [end](const auto& b){ return b.first < end; });
        if (less != more) return false;
        list.insert(more, {start, end});
        return true;
    }
};