Calender 2

 

Approach 2: Line Sweep

Intuition

The previous approach works well for the given problem, where we need to avoid triple bookings. However, if the requirements change such as checking for four overlapping bookings, the method becomes less flexible. We'd need to introduce additional lists, for example, to track triple bookings, making the solution harder to maintain and extend.

To address this, we can use a more flexible and standard solution: the Line Sweep algorithm. This approach is common for interval-related problems and can easily handle changes, such as checking for four or more overlapping bookings.

The Line Sweep algorithm works by marking when bookings start and end. For each booking (start, end), we mark the start point by increasing its count by 1 (indicating a booking begins), and we mark the end point by decreasing its count by 1 (indicating a booking ends). These marks are stored in a map, which keeps track of the number of bookings starting or ending at each point.

Once all bookings are processed, we compute the prefix sum over the map. The prefix sum at any point tells us how many active bookings overlap at that moment. If the sum at any point exceeds 2, it means we have a triple booking. At this point, the function should return false to prevent adding a new booking. If no triple booking is found, the function returns true, and the booking is allowed.

This approach is easily extendible. If we wanted to check for four or more bookings instead of three, we would simply adjust the threshold from 2 to 3 when calculating the prefix sum. This flexibility makes the Line Sweep method a more robust solution for variations of the problem.

fig

Algorithm

  1. Class MyCalendarTwo will have two data members, maxOverlappedBooking which is the maximum number of concurrent bookings possible at a time, and bookingCount which is a map from integer to integer with the time point as the key and number of bookings as the value.

  2. Initialize maxOverlappedBooking as 2, as we need to check for triple booking.

  3. Define the function book(start, end) as:

    • Increase the number of bookings for the time start and decrease the number of bookings for end by 1 in the map bookingCount.
    • Iterate over each key-value pair in the map in ascending order of keys to find the prefix sum. Add the value in the map to the count overlappedBooking.
    • If overlappedBooking is more than two, it implies that this is triple booking. Hence, we should return false. Also, we need to revert the changes in the map as this booking shouldn't be added.
    • If we reach here, it implies no triple booking and hence returns true.

Comments

Post a Comment

Popular posts from this blog

LeetCode 3Sum

Question Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Brute force We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:
Read more

New start Day 2 (1/10/2020) codeforces 492B Vanya and Lantern

 question: (source: https://codeforces.com/problemset/problem/492/B)      Vanya And Lantern Vanya walks late at night along a straight street of length  l , lit by  n  lanterns. Consider the coordinate system with the beginning of the street corresponding to point  0 , and its end corresponding to the point  l . Then the  i -th lantern is at the point  a i . The lantern lights all points of the street that are at the distance of at most  d  from it, where  d  is some positive number, common for all lanterns. Vanya wonders: what is the minimum light radius  d  should the lanterns have to light the whole street? Input The first line contains two integers  n ,  l  ( 1 ≤  n  ≤ 1000 ,  1 ≤  l  ≤ 10 9 ) — the number of lanterns and the length of the street respectively. The next line contains  n  integers  a i  ( 0 ≤  a i  ≤  l ). Multiple lanterns can be loca...
Read more

Heap (min)

 Heap Heap is a data structure used to store numbers in form of binary tree i.e each node has two children. Heap is the data structure behind PriorityQueue. Insert and pop operation inside a heap is oh log(n) complexity and can be used in multiple insert and pop operation questions. It is efficient and used in fastest sorting as well as sorting only takes nlog(n) complexity at worst case. Important Functions for heap: 1.  Heapify: This function is a top down approach to set an given array into heap. The idea is to set the top priority Item at the parent node of given subtree of 3. We will compare priority of left item from parent and then from right item to that of winner of parent and left and then swap the top priority with parent item. If top priority wasn't the parent item then we call the heapify again for the right or left node with which the value was swapped. If we have a given array then we can run a loop into that array from bottom of tree to top (excluding leafs),i....
Read more