Managing Merge Intervals

1. Working with Interval Format

Property	Description	Example
start	Start point of the interval	`1`
end	End point of the interval	`5`

Example: Define Interval Object

const interval = {
  start: 1,
  end: 5
};

Example: Create Interval Array

const intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 6 },
  { start: 8, end: 10 },
  { start: 15, end: 18 }
];

Note: Intervals are typically represented as objects with start and end properties.

2. Merging Overlapping Intervals

Property	Description	Example
intervals	Array of intervals represented as [start, end]	`[[1, 3], [2, 6], [8, 10]]`
merged	Resulting array after merging overlapping intervals	`[[1, 6], [8, 10]]`

Example: Merge Overlapping Intervals

const merge = (intervals) => {
  if (intervals.length <= 1) return intervals;

  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];

    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
  }

  return merged;
};

// Input
const intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
// Output
console.log(merge(intervals)); // [[1, 6], [8, 10], [15, 18]]

Note: The algorithm assumes intervals are sorted by start time. If not, sort them first.

3. Inserting New Interval

Property	Description	Example
intervals	List of non-overlapping intervals sorted by start time	`[[1,3],[6,9]]`
newInterval	New interval to be inserted	`[2,5]`

Example: Insert Interval

function insert(intervals, newInterval) {
  const result = [];
  let i = 0;
  const n = intervals.length;

  // Add all intervals before newInterval
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Merge overlapping intervals
  while (i < n && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }

  result.push(newInterval);

  // Add remaining intervals
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

// Example usage:
const intervals = [[1,3],[6,9]];
const newInterval = [2,5];
console.log(insert(intervals, newInterval)); // [[1,5],[6,9]]

Note: The algorithm handles merging overlapping intervals by comparing start and end times.

4. Finding Interval Intersections

Property	Description	Example
interval1	First interval represented as [start, end]	`[1, 3]`
interval2	Second interval represented as [start, end]	`[2, 4]`
intersection	Resulting intersection interval [start, end]	`[2, 3]`

Example: Finding Intersection of Two Intervals

function findIntersection(interval1, interval2) {
  const start = Math.max(interval1[0], interval2[0]);
  const end = Math.min(interval1[1], interval2[1]);

  if (start <= end) {
    return [start, end];
  }
  return [];
}

// Example usage
const interval1 = [1, 3];
const interval2 = [2, 4];
console.log(findIntersection(interval1, interval2)); // Output: [2, 3]

Note: If the start of the intersection is greater than the end, there is no overlap.

5. Checking Conflicting Appointments

Property	Description	Example
intervals	List of appointment intervals as [start, end]	`[[1, 4], [2, 5], [7, 9]]`
hasConflict	Boolean indicating if any intervals overlap	`true`

Example: Check for Conflicting Appointments

function hasConflictingAppointments(intervals) {
  for (let i = 0; i < intervals.length; i++) {
    for (let j = i + 1; j < intervals.length; j++) {
      const [start1, end1] = intervals[i];
      const [start2, end2] = intervals[j];

      if (start1 < end2 && start2 < end1) {
        return true;
      }
    }
  }
  return false;
}

const appointments = [[1, 4], [2, 5], [7, 9]];
console.log(hasConflictingAppointments(appointments)); // true

Note: This approach uses nested loops to compare every interval with every other. For better performance, consider sorting intervals by start time first.

6. Finding Minimum Meeting Rooms

Property	Description	Example
Input	List of meeting intervals [start, end]	`[[0,30],[5,10],[15,20]]`
Output	Minimum number of rooms required	`2`

Example: Finding Minimum Meeting Rooms

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;

  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0;
  let endPointer = 0;

  for (let i = 0; i < starts.length; i++) {
    if (starts[i] < ends[endPointer]) {
      rooms++;
    } else {
      endPointer++;
    }
  }

  return rooms;
}

const intervals = [[0,30],[5,10],[15,20]];
console.log(minMeetingRooms(intervals)); // Output: 2

Note: This approach uses two pointers to simulate the room allocation process efficiently.

7. Finding Employee Free Time

Property	Description	Example
intervals	List of intervals representing employee working hours	`[[1, 3], [5, 6], [7, 9]]`
freeTime	Intervals representing free time for employees	`[[3, 5], [9, 10]]`

Example: Find Free Time for Employees

function findEmployeeFreeTime(schedule) {
  const intervals = schedule.flat().sort((a, b) => a[0] - b[0]);
  const freeTime = [];
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (start > lastEnd) {
      freeTime.push([lastEnd, start]);
    }
    lastEnd = Math.max(lastEnd, end);
  }

  return freeTime;
}

const schedule = [
  [[1, 3], [5, 6]],
  [[2, 4], [7, 9]]
];

console.log(findEmployeeFreeTime(schedule)); // [[3, 5], [9, 10]]

Note: This approach assumes intervals are non-overlapping and sorted by start time.

Algorithm Summary

Merge all intervals from all employees
Sort merged intervals by start time
Find gaps between consecutive intervals
Return these gaps as free time slots

8. Finding Maximum CPU Load

Property	Description	Values
intervals	List of CPU intervals with start and end times	`[[1,4], [2,5], [7,9]]`
maxLoad	Maximum CPU load at any point in time	`2`

Example: Calculate Maximum CPU Load

function findMaxCPULoad(intervals) {
  const events = [];
  for (const [start, end] of intervals) {
    events.push({ time: start, type: 'start' });
    events.push({ time: end, type: 'end' });
  }

  events.sort((a, b) => {
    if (a.time === b.time) return a.type === 'start' ? -1 : 1;
    return a.time - b.time;
  });

  let currentLoad = 0;
  let maxLoad = 0;

  for (const event of events) {
    if (event.type === 'start') {
      currentLoad++;
    } else {
      currentLoad--;
    }
    maxLoad = Math.max(maxLoad, currentLoad);
  }

  return maxLoad;
}

const intervals = [[1,4], [2,5], [7,9]];
console.log(findMaxCPULoad(intervals)); // Output: 2

Note: This algorithm uses an event-based approach to track CPU load changes over time.

9. Removing Covered Intervals

Property	Description	Example
interval	An interval represented as [start, end]	`[1, 3]`
covered	Indicates if an interval is fully contained within another	`true`

Example: Identifying Covered Intervals

const intervals = [[1, 4], [2, 3], [5, 7], [6, 8]];
const covered = [];

for (let i = 0; i < intervals.length; i++) {
  const current = intervals[i];
  let isCovered = false;

  for (let j = 0; j < intervals.length; j++) {
    if (i !== j) {
      const other = intervals[j];
      if (other[0] <= current[0] && other[1] >= current[1]) {
        isCovered = true;
        break;
      }
    }
  }

  if (isCovered) {
    covered.push(current);
  }
}

console.log(covered); // [[2, 3]]

Note: An interval [a, b] is covered by [c, d] if c <= a and d >= b.

10. Finding Non-overlapping Intervals

Property	Description	Example
intervals	List of intervals represented as [start, end]	`[[1, 3], [2, 6], [8, 10]]`
non-overlapping	Set of intervals with no overlaps	`[[1, 3], [8, 10]]`

Example: Finding Non-overlapping Intervals

function findNonOverlapping(intervals) {
  if (intervals.length <= 1) return intervals;

  // Sort intervals by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const current = intervals[i];

    // If current interval does not overlap with last
    if (last[1] < current[0]) {
      result.push(current);
    } else {
      // Merge overlapping intervals
      last[1] = Math.max(last[1], current[1]);
    }
  }

  return result;
}

// Example usage
const intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
console.log(findNonOverlapping(intervals)); // [[1, 6], [8, 10], [15, 18]]

Note: This approach merges overlapping intervals to find the minimal set of non-overlapping intervals.