Logic Explained: Meeting Scheduler - Leetcode [Java] using Two Pointers
Tags: java, coding, leetcode, algorithms
Published: 2021-04-14 01:02:40

---
title: Logic Explained: Meeting Scheduler - Leetcode [Java] using Two Pointers
published: true
description: coding challenge - two pointers
tags: java, coding, leetcode, algorithms
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/79ftek9piie0934s1kzx.png
 
---

### Follow Me, Shout Out, or Give Thanks! 
Please :sparkling_heart: this article. a small thing to keep me motivated =)
Twitter: [@djjasonclark](https://twitter.com/djjasonclark)
Linkedin: [in/clarkngo](https://www.linkedin.com/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<sup>3</sup>) or O(n<sup>2</sup>) 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`.<br/>
a. Initialize/reinitialize two arrays to hold the current slot for each co-worker.<br/>
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.<br/>
c. **If** duration is within the range of max start time and min end time, then return start time and start time + duration.<br/>
   **Else if** end time of co-worker **A** less than the end time of co-worker **B**, then increment co-worker **A**'s pointer.<br/>
   **Else if** end time of co-worker **B** less than the end time of co-worker **A**, then increment co-worker **B**'s pointer.<br/>
   **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.
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ztztdmsldwpvqxaj52xo.png)
 
##### 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.
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iulry90d8eatwec2oojs.png)
 

##### 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.
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/szaf9dbicr8zgm41ueyz.png)
 
### 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<>();
    }
}
```