# LeetCode: my calender 2 C#

https://leetcode.com/problems/my-calendar-ii/

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar. Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); //returns true


Explanation:

• The first two events can be booked. The third event can be double booked.
• The fourth event (5, 15) can't be booked, because it would result in a triple booking.
• The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
• The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event; the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000. In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

Please review for style and performance

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
[TestClass]
public class MyCalender2Test
{
[TestMethod]
public void TestMethod1()
{
MyCalendarTwo myCalendar = new MyCalendarTwo();
Assert.IsTrue(myCalendar.Book(10, 20)); // returns true
Assert.IsTrue(myCalendar.Book(50, 60)); // returns true
Assert.IsTrue(myCalendar.Book(10, 40)); // returns true
Assert.IsFalse(myCalendar.Book(5, 15)); // returns false
Assert.IsTrue(myCalendar.Book(5, 10)); // returns true
Assert.IsTrue(myCalendar.Book(25, 55)); // returns true
}
}

public class MyCalendarTwo
{
private SortedDictionary<int, int> _dict;
public MyCalendarTwo()
{
_dict = new SortedDictionary<int, int>();
}

/// <summary>
/// foreach start you add a pair of (start,1)
/// foreach end you add a pair of (end,-1)
/// the list is sorted we add and remove events.
/// if we can more then 3 events added at the same time.
/// we need to remove the event
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <returns></returns>
public bool Book(int start, int end)
{
//   s1------e1
// s-----e
//      s---e
// s------------e
//      s---------e
//s--e good
//               s--e

if(!_dict.TryGetValue(start, out var temp))
{
}
else
{
_dict[start]++;
}

if (!_dict.TryGetValue(end, out var temp1))
{
}
else
{
_dict[end]--;
}

int active = 0;
foreach (var d in _dict.Values)
{
active += d;
if (active >= 3)
{
_dict[start]--;
_dict[end]++;
if (_dict[start] == 0)
{
_dict.Remove(start);
}

return false;
}
}

return true;
}
}

/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* bool param_1 = obj.Book(start,end);
*/
}

• Please do not update the code in your question after receiving answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Mast
Aug 11, 2020 at 21:32

Not too much to say on style, it all reads well to me. That said, there are a couple things I'd change.

You can get away with _dict as a field here but I think _bookings would be slightly nicer.

if(!_dict.TryGetValue(start, out var temp))
{
}
else
{
_dict[start]++;
}


I believe you could do:

var existingCount = _bookings.TryGetValue(start, out var count) ? count : 0;
_bookings[start] = existingCount + 1;


You could also filter your list when you iterate. Once you get to the end of the booking you're currently looking at, you don't need to keep going.

foreach (var d in _bookings.TakeWhile(kvp => kvp.Key < end).Select(kvp => kvp.Value))


It would be nice if you didn't have to add the start and end in to the dictionary but it does seem to be the simplest solution here. This can be a dangerous strategy because you have to ensure the entries you've added are always removed but I can't see any way your code can throw in the loop.

• thanks you very much i appreciate the review Aug 11, 2020 at 8:03

Because the default value is returned for the value parameter in _dict.TryGetValue() if it returns false and the default value for int is 0 it should be save to do:

  _dict.TryGetValue(start, out int count);
_dict[start] = count + 1;
_dict.TryGetValue(end, out count);
_dict[end] = count - 1;


As a micro optimization, you can reduce this:

      _dict[start]--;
if (_dict[start] == 0)
{
_dict.Remove(start);
}


to

      if (_dict[start] == 1)
_dict.Remove(start);
else
_dict[start]--;


so that at least when you can remove start you do one operation less (two instead of three).

I wonder if you can remove end as well if it becomes 0 when incrementing it if active >= 3?

• I had wondered about doing that with the dictionary too but I wasn't sure the value of the out parameter was specified when the method returns false. It is and you're quite right that it's default(TValue) so 0 for the int. I'm never sure about code that ignores a return value but I think it's fine here. Nice observation.
– RobH
Aug 11, 2020 at 19:31
• @Henrik Hansen yes i can remove end as well. i just missed it when uploaded the code. i fixed it later. Aug 11, 2020 at 21:28