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);
     */
}

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?