Logic Explained: Meeting Scheduler - Leetcode [Java] using Two Pointers

Follow Me, Shout Out, or Give Thanks!

Please 💖 this article. a small thing to keep me motivated =)
Twitter: @djjasonclark
Linkedin: in/clarkngo

Description

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration, return the earliest time slot that works for both of them and is of duration.

If there is no common time slot that satisfies the requirements, return an empty array.

Example 1

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Example 2

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Scenario

Today, your two coworkers need to meet for a specific time duration at the earliest available time. Both of them gave you a list of open slots in their day. You are tasked to find overlapping slots (open slot of co-worker A and open slot co-worker B) the would allow them to have a meeting given the time duration of the meeting.

Logic

1. Look at co-worker A available slot AND compare it with co-worker B available slot.

2. If the available slot range is not within the meeting time duration, look for the next available slot of a co-worker.

Question: Which co-worker's next available slot should we look at first to compare with the other co-worker's current available slot?

Answer: The co-worker, with the lower end time for its current available slot compared to the other co-worker's end time for its current available slot, is the one we should check for the next available slot.

Algorithm: Two Pointer Technique

• Use of two pointers in a loop.
• Helps reduce the time complexity of O(n³) or O(n²) to O(n) with just one loop.

Pseudocode

1. Sort the slots1 and slots2 array in ascending order of the starting time. Use Arrays.sort() with Comparator in the 2nd parameter.

2. Initialize two pointers at index 0.

3. While pointer for the length of slots1 is less than the length of slots1 and pointer for the length of slots2 is less than the length of slots2.
   
   a. Initialize/reinitialize two arrays to hold the current slot for each co-worker.
   
   b. Initialize/reinitialize two integers: 1) to store the max start time between two co-worker's current available slots. 2) to store the minimum end time between two co-worker's current available slots.
   
   c. If duration is within the range of max start time and min end time, then return start time and start time + duration.
   
   Else if end time of co-worker A less than the end time of co-worker B, then increment co-worker A's pointer.
   
   Else if end time of co-worker B less than the end time of co-worker A, then increment co-worker B's pointer.
   
   Else increment both co-workers A and B's pointers.

4. Return empty array. No overlapping slots the would allow the co-workers to have a meeting given the time duration of the meeting.

Scenarios

Scenario 1: the end time of Co-worker A’s end time overlaps Co-worker B’s start time.

HOWEVER, overlap is NOT sufficient to cover meeting duration.

Scenario 2: the end time of Co-worker B’s end time overlaps Co-worker A’s start time.

HOWEVER, overlap is NOT sufficient to cover meeting duration.

Scenario 3: the end time of Co-worker B’s end time overlaps Co-worker A’s start time (or vice-versa).

AND, overlap is sufficient to cover meeting duration.

Code

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a,b)-> a[0]-b[0]);
        Arrays.sort(slots2, (a,b)-> a[0]-b[0]);

        int p1 = 0;
        int p2 = 0;

        while (p1 < slots1.length && p2 < slots2.length) {
            int[] curr1 = slots1[p1];
            int[] curr2 = slots2[p2];

            int start = Math.max(curr1[0], curr2[0]);
            int end = Math.min(curr1[1], curr2[1]);

            if (end - start >= duration) 
                return Arrays.asList(start,start+duration);
            else if (curr1[1] < curr2[1]) p1++;
            else if (curr2[1] < curr1[1]) p2++;
            else {
                p1++;
                p2++;
            }

        }
        return new ArrayList<>();
    }
}