Iteration

Cancel Meetings

You're given the head of a Linked List head. Each node in the Linked List contains an interval, representing the start and end time of a meeting. Nodes in the Linked List are sorted based on their starting time, and do not overlap.

A new meeting just came up for you, meeting, and you decide to cancel all the meetings that conflict with it. Return the head of a Linked List representing the new meeting times. The Linked List must remain sorted by start time. If all the meetings must be canceled, return None.

Details: The given Linked List will contain at least one node. It's fine if a meeting starts right when another one ends.

Example:

\notag \def\l#1{\texttt{#1}} \begin{align*} & \l{intervals = } \texttt{ListNode.of}\Bigg(\Big[ \l{[0,2], [3,4], [5,7], [8,10], [11,13]} \Big]\Bigg)\\ & \l{meeting = [1, 11]} \\[8bp] & \l{=> returns ListNode.of([[11,13]])} \end{align*}

Explanation: You have to cancel the 0th, 1st, 2nd, and 3rd interval, because they overlap with the meeting. Here's a visual of this, where the intervals are shown in black, and the meeting is shown in green:

First Few Test Cases:

To solve this problem, you have to find the leftmost and rightmost intervals that overlap with the meeting, and delete them and everything in between.

To delete the two yellow intervals and everything in between, we want to point the node immediately before the leftmost overlap, to the node immediately after the rightmost overlap. That way, the Linked List will completely skip over all of these intervals that conflict with the meeting.

You can find leftmost overlapping interval by iterating left to right until you reach it. Here's the code for this:

When this loop is finished, curr is the leftmost overlap (yellow), and prev is the node before it:

Next, you need to find the rightmost overlap. You can do this by looping over the remaining intervals until you get to an interval that no longer overlaps the meeting. Here's the code for this:

Now we have the interval before the meeting prev and the interval after the meeting curr, and we can point the previous node to the current one to solve the problem. Here's how you code this up:

Time Complexity $O(n)$ . We loop through all the elements in the intervals array.

Space Complexity $O(n)$ . We store an array with O(n) elements.

Mark as Completed:

Submits:

cancelMeetings

Imports:

ListNode

Test your code to get an output here!

cancelMeetings(

)

Test your code to get an output here!