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:

cancelMeetings(ListNode.of([[0, 1], [1, 3]]), [2, 3])
# ListNode.of([[0, 1]])

cancelMeetings(ListNode.of([[0, 1], [1, 2]]), [0, 3])
# None

cancelMeetings(ListNode.of([[0, 2], [3, 4], [5, 7], [8, 10], [11, 13]]), [1, 11])
# ListNode.of([[11, 13]])

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:

curr = head # this will be the leftmost overlapping node
prev = None # this will be the node before it

# stop looping when interval overlaps start of meeting
while curr:
    if curr.val[1] > meeting[0]: break
    prev = curr
    curr = curr.next

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:

# if the interval no longer overlaps the meeting, then stop looping 
while curr:
    if curr.val[0] >= meeting[1]: break
    curr = curr.next

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:

def cancelMeetings(head, meeting):

    curr = head
    prev = None

    # finds `prev`
    while curr:
        if curr.val[1] > meeting[0]: break
        prev = curr
        curr = curr.next
    
    # finds `curr`
    while curr:
        if curr.val[0] >= meeting[1]: break
        curr = curr.next


    # at the end, if there was no previous to the leftmost node, just return rightmost node as the head
    if not prev:
        return curr

    # skip over all the meetings that overlap, and return the head
    prev.next = curr
    return head

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!