Sweep line algorithm on intervals related problems

What is the Sweep line algorithm?

If we have data given in intervals, then we can take a vertical line and sweep it across to find out the answer. There are four phases to run this algorithm.

1. Convert interval data into an events tuple array.
2. Sort events array to simulate the interval sorting.
3. Iterate values in an events array to run sweep line
4. Calculate answer.

The main complexity of Sweepline algorithm is to find out the right sorting order on events.

Let’s go through a few problems to understand this better.

Total duration where number of people in the hall is greater than k

For given [arrival, departure] time for a person in a hall, we need to find out the total duration when more than k people were in the hall.

For [50,80],[80,90] , we want to first process 80 as departure time therefore to build events we will use [arrival, +1] and [departure, -1] .

/**
 * @param {number[][]} intervals
 * @param {number} k
 * @return {number}
 */
var totalDuration = function (intervals, k) {
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);
        events.push([end, -1]);
    }
    events.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        }
        return a[1] - b[1];
    });
    let ans = 0;
    let counter = 0;
    for (let i = 0; i < events.length; i++) {
        const [time, type] = events[i];
        counter += type;
        if (counter >= k) {
            const [next_time, next_type] = events[i + 1];
            ans += (next_time - time);
        }
    }
    return ans;
};

Offline query to get the sum of top k for a given interval y

Here we have given [left, right, x] as [[1,9,1],[3,10,3],[5,7,2],[11,19,5],[13,15,6]]and the list of intervals to perform queries as [[2,2],[4,2],[6,2],[14,2]] where each query is represented as [y,k]. We need to find the top k sum for a given interval y . Answer should be [1, 4, 5,11]

Here we have three types of interval values

1. left
2. right
3. y

To preserve data we need to store each ith [left, right, x] as [left, ?, x, i] and [right,?, x, i] . Similarly, queries can be stored in events as [y,?, k,i] . Now the question is what should be the sorting order to choose value for ? .

It is always easy to decide when we compare the equal time values for each type. Let's say [p,?,x,i],[p,?,x,i],[p,?,k,i] for left, right, and query. Which one do we want to process first?

Since we would like to run the query before the end time, and after the start, therefore, we can go with start:0 , query:1 and end:2 .

class SortedMultiset {
  constructor() {
    this.keys = [];
    this.map = new Map();
  }

  // Add a key or increment its count if it already exists
  add(key) {
    const index = this.binarySearch(key);
    if (index >= 0) {
      this.map.set(key, this.map.get(key) + 1);
    } else {
      this.keys.splice(-index - 1, 0, key);
      this.map.set(key, 1);
    }
  }

  // Remove a key and decrement its count
  delete(key) {
    const index = this.binarySearch(key);
    if (index >= 0) {
      const count = this.map.get(key);
      if (count > 1) {
        this.map.set(key, count - 1);
      } else {
        this.keys.splice(index, 1);
        this.map.delete(key);
      }
    }
  }

  // Get the count of a key
  getCount(key) {
    return this.map.get(key) || 0;
  }

  // Binary search to find the insertion position or key's index
  binarySearch(key) {
    let low = 0;
    let high = this.keys.length - 1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      const midKey = this.keys[mid];
      if (midKey === key) {
        return mid;
      } else if (midKey < key) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return -(low + 1); // Not found, return negative insertion index
  }

  // Iterator for the multiset
  [Symbol.iterator]() {
    let index = 0;
    let currentKey = this.keys[index];
    let count = this.map.get(currentKey) || 0;

    return {
      next: ()=> {
        if (count > 0) {
          count--;
          return { value: currentKey, done: false };
        } else if (index < this.keys.length - 1) {
          index++;
          currentKey = this.keys[index];
          count = this.map.get(currentKey) || 0;
          return { value: currentKey, done: false };
        } else {
          return { done: true };
        }
      },
    };
  }
}
/**
 * @param {number[][]} intervals
 * @param {number[][]} queries
 * @return {number}
 */
var topKQuery = function (intervals, queries) {
  // 0: start, 1: query, 2: end
  const events = []; // {time, type, x, i}
  for (let i = 0; i < intervals.length; i++) {
    const [start, end, x] = intervals[i];
    events.push([start, 0, x, i]);
    events.push([end, 2, x, i]);
  }
  for (let i = 0; i < queries.length; i++) {
    const [y, k] = queries[i];
    events.push([y, 1, k, i]);
  }
  // Now sort it
  events.sort((a, b) => {
    if (a[0] !== b[0]) {
      return a[0] - b[0];
    }
    return a[1] - b[1];
  });
  const multiset = new SortedMultiset();
  const ans = new Map();
  for (let j = 0; j < events.length; j++) {
    const [time, type, x, i] = events[j];
    if (type === 0) {
      // start interval, add score
      multiset.add(-x); // insert negative for decreasing
    } else if (type === 2) {
      // end interval, delete score
      multiset.delete(-x);
    } else {
      // Query
      let local = 0;
      let counter = 0;
      for (const key of multiset) {
          local += -key; // reverse sign
          counter++;
          if (counter === x) {
            break;
          }
      }
      ans.set(i, local);
    }
  }
  return queries.map(([y, k], i) => ans.get(i));
};

const intervals = [[1,9,1],[3,10,3],[5,7,2],[11,19,5],[13,15,6]];
const queries = [[2,2],[4,2],[6,2],[14,2]];
console.log(topKQuery(intervals, queries));

Note: If the question is changed to exclude the boundary then we need to take the type as end:0, query: 2, start:2

Offline query to get the max score for a given interval y

Here we have given [left, right, x] as [[1,9,1],[3,10,3],[5,7,2],[11,19,5],[13,15,6]]and the list of intervals to perform queries as [2,4,6,14] where each query is represented as [y]. We need to find the max score for a given interval y . Answer should be [1, 3, 3,6] .

class SortedMultiset {
  constructor() {
    this.keys = [];
    this.map = new Map();
  }

  // Add a key or increment its count if it already exists
  add(key) {
    const index = this.binarySearch(key);
    if (index >= 0) {
      this.map.set(key, this.map.get(key) + 1);
    } else {
      this.keys.splice(-index - 1, 0, key);
      this.map.set(key, 1);
    }
  }

  // Remove a key and decrement its count
  delete(key) {
    const index = this.binarySearch(key);
    if (index >= 0) {
      const count = this.map.get(key);
      if (count > 1) {
        this.map.set(key, count - 1);
      } else {
        this.keys.splice(index, 1);
        this.map.delete(key);
      }
    }
  }

  // Get the count of a key
  getCount(key) {
    return this.map.get(key) || 0;
  }

  // Binary search to find the insertion position or key's index
  binarySearch(key) {
    let low = 0;
    let high = this.keys.length - 1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      const midKey = this.keys[mid];
      if (midKey === key) {
        return mid;
      } else if (midKey < key) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return -(low + 1); // Not found, return negative insertion index
  }

  // Iterator for the multiset
  [Symbol.iterator]() {
    let index = 0;
    let currentKey = this.keys[index];
    let count = this.map.get(currentKey) || 0;

    return {
      next: ()=> {
        if (count > 0) {
          count--;
          return { value: currentKey, done: false };
        } else if (index < this.keys.length - 1) {
          index++;
          currentKey = this.keys[index];
          count = this.map.get(currentKey) || 0;
          return { value: currentKey, done: false };
        } else {
          return { done: true };
        }
      },
    };
  }
}
/**
 * @param {number[][]} intervals
 * @param {number[][]} queries
 * @return {number}
 */
var topKQuery = function (intervals, queries) {
  // 0: start, 1: query, 2: end
  const events = []; // {time, type, x, i}
  for (let i = 0; i < intervals.length; i++) {
    const [start, end, x] = intervals[i];
    events.push([start, 0, x, i]);
    events.push([end, 2, x, i]);
  }
  const k = 1; // use k= 1
  for (let i = 0; i < queries.length; i++) {
    const [y, 1] = queries[i];
    events.push([y, 1, k, i]);
  }
  // Now sort it
  events.sort((a, b) => {
    if (a[0] !== b[0]) {
      return a[0] - b[0];
    }
    return a[1] - b[1];
  });
  const multiset = new SortedMultiset();
  const ans = new Map();
  for (let j = 0; j < events.length; j++) {
    const [time, type, x, i] = events[j];
    if (type === 0) {
      // start interval, add score
      multiset.add(-x); // insert negative for decreasing
    } else if (type === 2) {
      // end interval, delete score
      multiset.delete(-x);
    } else {
      // Query
      let local = 0;
      let counter = 0;
      for (const key of multiset) {
          local += -key; // reverse sign
          counter++;
          if (counter === x) {
            break;
          }
      }
      ans.set(i, local);
    }
  }
  return queries.map(([y, k], i) => ans.get(i));
};

const intervals = [[1,9,1],[3,10,3],[5,7,2],[11,19,5],[13,15,6]];
const queries = [[2,2],[4,2],[6,2],[14,2]];
console.log(topKQuery(intervals, queries));

Meeting Rooms

https://leetcode.com/problems/meeting-rooms/description/

The goal here is to check if a person can attend all the meetings or not.

Solution

A person can only not able to attend a meeting if there is overlap with others. We need to find out if there is any overlap between any meetings.

Input intervals of each meeting are given in [start,end] format. Convert it into [start, 0] and [end, 1] tuple array. Apply the following sorting.

Following is code to solve this problem.

/**
 * @param {number[][]} intervals
 * @return {boolean}
 */
var canAttendMeetings = function(intervals) {
    // Build events array
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]); // +1 represent start
        events.push([end, -1]); // -1 represent end
    }
    // sort events
    events.sort((a, b) => {
        if(a[0] !== b[0]) {
            return a[0] - b[0]; // increasing order based on time
        }
        // if time is same then keep end time before start time so that we can first finish processing last interval end time before we process next starting interval
        return a[1] - b[1]; 
    });
    
    // Apply sweep line
    let counter = 0;
    for (const [time, type] of events) {
        // Update counter
        counter+= type;
        // check for voilation 
        if(counter > 1) {
            return false;
        }
        
    }
    return true;
};

Union of all and intersection of all

For given intervals [start, end] find the

Length of union or intersection

const lengthOfUnionOrIntersection = intervals => {
    const n = intervals.length;
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);
        events.push([end, -1]);
    }
    events.sort((a, b)=> {
        if(a[0] !== b[0]) {
            return a[0] - b[0];
        }
        return a[1] - b[1];
    });
    let counter = 0;
    let union =0;
    let intersection = 0;
    for (let i=0; i < events.length - 1; i++) {
        const [time, type] = events[i];
        counter += type;
        if(counter > 0) {
            union += events[i+1][0] - events[i][0];
        }
        if(counter === n) {
            intersection += events[i+1][0] - events[i][0];
        }
    }
    return {union, intersection};
}
console.log(lengthOfUnionOrIntersection([[1,4],[3,6]]))

Meeting Rooms II

https://leetcode.com/problems/meeting-rooms-ii/description/

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Approach

If there is no interval between two meetings then we just need one conference room to conduct the meeting. If there is overlap then we need that many conference rooms to conduct the meeting. We need to track the maximum overlap for meetings.

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function(intervals) {
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);
        events.push([end, -1]);
    }
    events.sort((a, b)=>{
        if(a[0] !== b[0]) {
            return a[0] - b[0];
        }
        return a[1] - b[1];
    });
    let ans = 0;
    let counter = 0;
    for (const [time, type] of events) {
        counter+= type;
        ans = Math.max(ans, counter);
    }
    return ans;
};

Meeting scheduler

https://leetcode.com/problems/meeting-scheduler/description/

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

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

The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

Example 1:

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

Approach:

/**
 * @param {number[][]} slots1
 * @param {number[][]} slots2
 * @param {number} duration
 * @return {number[]}
 */
var minAvailableDuration = function (slots1, slots2, duration) {
    const events = [];
    for (const [start, end] of slots1) {
        events.push([start, 1, 1]);
        events.push([end, -1, 1]);
    }
    for (const [start, end] of slots2) {
        events.push([start, 1, 2]);
        events.push([end, -1, 2]);
    }
    events.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        }
        if (a[1] !== b[1]) {
            return a[1] - b[1];
        }
        return a[2] - b[2];
    })
    let active = 0;
    let last = [];
    for (const [time, type, person] of events) {
        if (type == 1) {
            last = [time, type, person];
        } else {
            if (active >= 2 && time - last[0] >= duration) {
                return [last[0], last[0] + duration];
            }
        }
        active += type;
    }
    return [];
};

Restaurant Customers

Restaurant Customers

The goal here is to find out the maximum number of customers in the restaurant at any time.

Solution:

[arrival,departure] for each customer are given. We can represent events as [arrival,x],[departure, y]. If all numbers are different then it's easy to sort. Let’s see the case when the ending time is the same as the start time

[80,90],[90,100] has the answer 1. After sorting we will have two possibilities[{80,x},{90,x},{90,y},{100,y}] or [{80,x}, {90, y}, {90, x}, {100, y}]. Which one to choose?

We want to count the maximum number of customers in the restaurant at any time. There it is required to keep the departure time first then the arrival time. It means we need to choose {arrival, +1} and {departure, -1} .

Following is code using the Sweepline algorithm.

/**
 * @param {number[][]} intervals
 * @return {boolean}
 */
var maxCustomers = function(intervals) {
    // Build events array
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]); // +1 represent start
        events.push([end, -1]); // -1 represent end
    }
    // sort events
    events.sort((a, b) => {
        if(a[0] !== b[0]) {
            return a[0] - b[0]; // increasing order based on time
        }
        // if time is same then keep end time before start time so that we can first finish processing last interval end time before we process next starting interval
        return a[1] - b[1]; 
    });

    // Apply sweep line
    let counter = 0;
    let ans = 0;
    for (const [time, type] of events) {
        // Update counter
        counter+= type;
        ans = Math.max(ans, counter);
        
    }
    return ans;
};

Remove interval

https://leetcode.com/problems/remove-interval/

Remove covered interval

https://leetcode.com/problems/remove-covered-intervals/

Container with most water

https://leetcode.com/problems/container-with-most-water/