7
\$\begingroup\$

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);
     */
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Mast Aug 11 at 21:32
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ thanks you very much i appreciate the review \$\endgroup\$ – Gilad Aug 11 at 8:03
2
\$\begingroup\$

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?

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – RobH Aug 11 at 19:31
  • 1
    \$\begingroup\$ @Henrik Hansen yes i can remove end as well. i just missed it when uploaded the code. i fixed it later. \$\endgroup\$ – Gilad Aug 11 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.