LeetCode: my calender 2 C#

Question

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))
 {
 _dict.Add(start, temp + 1);
 }
 else
 {
 _dict[start]++;
 }
 if (!_dict.TryGetValue(end, out var temp1))
 {
 _dict.Add(end, temp1 - 1);
 }
 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);
 */
}

• Mast: 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 .

Answer 1

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.

You can simplify the dictionary access too:

if(!_dict.TryGetValue(start, out var temp))
{
 _dict.Add(start, temp + 1);
}
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.

Answer 2

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?

• RobH: 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.
• Gilad: @Henrik Hansen yes i can remove end as well. i just missed it when uploaded the code. i fixed it later.