729. My Calendar I

Description

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

0 <= start < end <= 10⁹
At most 1000 calls will be made to book.

Solutions

Use a list to store the intervals of booking, which contains all intervals in sorted order. Each time book(int start, int end) is called, loop over the list of intervals to see whether the new interval [start, end) can be added.

If the new interval can be added at the start or at the end without causing a double booking, add the new interval at the start or at the end and return true.

If the new interval can be added between two intervals without causing a double booking, add the new interval between the two intervals and return true.

If the new interval has intersection with any interval in the list, then adding the interval will cause double booking, so return false.

import java.util.Map;
import java.util.TreeMap;

class MyCalendar {

    private final TreeMap<Integer, Integer> tm = new TreeMap<>();

    public MyCalendar() {
    }

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> ent = tm.floorEntry(start);
        if (ent != null && ent.getValue() > start) {
            return false;
        }
        ent = tm.ceilingEntry(start);
        if (ent != null && ent.getKey() < end) {
            return false;
        }
        tm.put(start, end);
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such: MyCalendar
 * obj = new MyCalendar(); boolean param_1 = obj.book(start,end);
 */

class MyCalendar {
public:
    map<int, int> m;

    MyCalendar() {
    }

    bool book(int start, int end) {
        ++m[start];
        --m[end];
        int s = 0;
        for (auto& [k, v] : m) {
            s += v;
            if (s > 1) {
                --m[start];
                ++m[end];
                return false;
            }
        }
        return true;
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

'''
>>> sd
SortedDict({'a': 111, 'b': 222, 'c': 333})
>>> sd.keys()
SortedKeysView(SortedDict({'a': 111, 'b': 222, 'c': 333}))
>>> sd.values()
SortedValuesView(SortedDict({'a': 111, 'b': 222, 'c': 333}))
>>> sd.items()
SortedItemsView(SortedDict({'a': 111, 'b': 222, 'c': 333}))
>>>
>>>
>>> sd.keys()[1]
'b'
>>> sd.values()[1]
222



>>> sd.append({'aaa':111})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'SortedDict' object has no attribute 'append'
>>>
>>> sd.add({'aaa':111})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'SortedDict' object has no attribute 'add'
'''

from sortedcontainers import SortedDict

class MyCalendar:
    def __init__(self):
        self.sd = SortedDict()

    def book(self, start: int, end: int) -> bool:
        # bisect_left will not work, due to duplicates
        # eg: [[],[10,20],[15,25],[20,30]]
        idx = self.sd.bisect_right(start)

        # self.sd.keys()[idx] ==> end time
        # self.sd.values()[idx] ==> it's start time
        if idx < len(self.sd) and end > self.sd.values()[idx]:
            return False
        self.sd[end] = start
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

############

class Node(object): # double linked list, full scan
    def __init__(self, s, e):
        self.s = s
        self.e = e
        self.left = None
        self.right = None

class MyCalendar(object):

    def __init__(self):
        self.root = None

    def book_helper(self, s, e, node):
        if node.e <= s:
            if node.right:
                return self.book_helper(s, e, node.right)
            else:
                node.right = Node(s, e)
                return True
        elif node.s >= e:
            if node.left:
                return self.book_helper(s, e, node.left)
            else:
                node.left = Node(s, e)
                return True
        else:
            return False

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        if not self.root:
            self.root = Node(start, end)
            return True
        else:
            return self.book_helper(start, end, self.root)


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

type MyCalendar struct {
	rbt *redblacktree.Tree
}

func Constructor() MyCalendar {
	return MyCalendar{
		rbt: redblacktree.NewWithIntComparator(),
	}
}

func (this *MyCalendar) Book(start int, end int) bool {
	if p, ok := this.rbt.Floor(start); ok && p.Value.(int) > start {
		return false
	}
	if p, ok := this.rbt.Ceiling(start); ok && p.Key.(int) < end {
		return false
	}
	this.rbt.Put(start, end)
	return true
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */

class MyCalendar {
    private calendar: number[][];

    constructor() {
        this.calendar = [];
    }

    book(start: number, end: number): boolean {
        for (const item of this.calendar) {
            if (end <= item[0] || item[1] <= start) {
                continue;
            }
            return false;
        }
        this.calendar.push([start, end]);
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */

use std::collections::BTreeMap;

struct MyCalendar {
    bt: BTreeMap<i32, i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCalendar {
    fn new() -> Self {
        MyCalendar {
            bt: BTreeMap::new(),
        }
    }

    fn book(&mut self, start: i32, end: i32) -> bool {
        if let Some((_, &val)) = self.bt.range(..=start).last() {
            println!("{} {} {}", start, end, val);
            if val > start {
                return false;
            }
        }
        if let Some((&key, _)) = self.bt.range(start..).next() {
            if key < end {
                return false;
            }
        }
        self.bt.insert(start, end);
        true
    }
}/**
 * Your MyCalendar object will be instantiated and called as such:
 * let obj = MyCalendar::new();
 * let ret_1: bool = obj.book(start, end);
 */

var MyCalendar = function () {
    this.calendar = [];
};

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function (start, end) {
    for (const item of this.calendar) {
        if (end <= item[0] || item[1] <= start) {
            continue;
        }
        return false;
    }
    this.calendar.push([start, end]);
    return true;
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */

729 - My Calendar I

729. My Calendar I

Description

Solutions

All Problems

All Solutions

Welcome to Subscribe On Youtube

729. My Calendar I

Description

Solutions

All Problems

All Solutions