Mock interview: 731 My calendar

July 9, 2020

Here is the gist.

	using System;
	// To execute C#, please define "static void Main" on a class
	// named Solution.
	class Solution
	{
	static void Main(string[] args)
	{
	for (var i = 0; i < 5; i++)
	{
	Console.WriteLine("Hello, World");
	}
	}
	}
	public class MyCalendarTwo {
	// store all events
	// sort all events by start time
	// determine if triple booking or not
	// if it is triple booking then return
	//
	private Sorted<int> sortedStartTime; // search start time - apply binary search
	private Dictionary<int, Sorted<int[]>> startTimeintervals; // key - start time
	private Dictionary<int, Sorted<int[]>> endTimeintervals; // key - start time
	public MyCalendarTwo() {
	intervals = new Dictionary<int, List<int[]>>();
	sortedStartTime = new Sorted<int>();
	}
	// given new event, triple book
	// all events overlap with new event
	// maximum event number
	// ------
	// ---------
	// -------
	// the above triple booking
	// A B
	// ------ ----------
	// C
	// ------- range
	// startA -> startC -> endA - startB -- endC
	// 1 1 -1 = 1 +1= 2 1
	// count <= 2 all the time from startA - endB, startC and endC
	// the above is not triple booking
	public bool Book(int start, int end) {
	if(start > end)
	return false;
	// determine if there is triple events - before add the interval to dictionary
	int count = 0;
	int currentTime = 0;
	foreach(var item in sortedStartTime)
	{
	var intervals = startTimeintervals[item];
	foreach(var endTime in intervals)
	{
	var startTime = item;
	// take care of end time - using
	// ----
	// ----------
	if(Math.Max(startTime, start) < Math.Min(endTime, end) > 0)
	{
	count++;
	if(count > 2)
	return false;
	}
	// count--
	}
	}
	// determine if two events are overlap
	}
	}
	/**
	* Your MyCalendarTwo object will be instantiated and called as such:
	* MyCalendarTwo obj = new MyCalendarTwo();
	* bool param_1 = obj.Book(start,end);
	*/
	find lowest common ancestor
	- https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/655518/C-various-topics-covered-in-2020-practice
	https://github.com/jianminchen/Leetcode_Julia/tree/master/Practice%20history/2020%20June%20to%20July%20Facebook%20phone%20screen
	/*
	1039
	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].
	*/

view raw Leetcode731_MyCalendarII.cs hosted with ❤ by GitHub

More content

I was thinking about how to add end time into my for loop, and end time should be sorted and mixed with start time as well.

To make things working, I should just using one Dictionary<int, int>. Do not separate start time from end time. And also we do not need to memorize all intervals with start time and end time. All we care about is how many intervals live in any time. We no longer need to record intervals inside class properties.

Clean and simple design is to use Dictionary<int, int>, key is start time or end time, value is the live interval count variable.