N/A | The Interval Covering Problem (Least Number of Visits)
big_gucci_sosa
386
JavaScriptinterview questionInterview

This is not a question that I was asked in an interview. This question is from Elements of Programming Interview (EPI) #17.3.

image

Here is a the summarized question:

Q: Given a set of closed intervals, find the minimum sized set of numbers that covers the intervals.

Example 1:  
Input: [[0,4],[2,8]]
Output: 1

Example 2: 
Input: [[1, 2], [2, 3], [3, 4], [2, 3], [3, 4], [4, 5]]
Output: 2

Here's what I got in JavaScript. It seems like it's working.

function intervalCoveringProblem(tasks) {
  const eSorted = tasks.sort((a, b) => a[1] - b[1]); // Sort by the "END"

  let numVisits = 1;
  let [_, lastReach] = eSorted.shift(); // Dequeue
  while (eSorted.length > 0) {
    const curTask = eSorted.shift();
	// If the current "START" does not intersect with lastReach
    if (lastReach < curTask[0]) {
      numVisits++;
      lastReach = curTask[1];
    }
  }
  return numVisits;
}

Time Complexity:
Assuming that the .shift() is O(1), the time complexity is dominated by the sort. O(n log(n))

Comments (0)