Implementing Line Sweep Algorithm

1. Applying Line Sweep Concept

Step	Description	Implementation
1. Define Events	Identify key points or intervals that trigger actions	`const events = [ { type: 'start', x: 10, y: 5 }, { type: 'end', x: 20, y: 5 } ];`
2. Sort Events	Sort events by x-coordinate to process in order	`events.sort((a, b) => a.x - b.x);`
3. Sweep Line Movement	Move a vertical line across the plane	`let sweepLine = 0; for (const event of events) { if (event.x > sweepLine) { sweepLine = event.x; } }`
4. Handle Events	Process events based on type and context	`if (event.type === 'start') { activeIntervals.add(event); } else if (event.type === 'end') { activeIntervals.delete(event); }`

Example: Finding Intersections

const intervals = [
  { start: 1, end: 5 },
  { start: 3, end: 7 },
  { start: 6, end: 9 }
];

let intersections = [];

for (let i = 0; i < intervals.length; i++) {
  for (let j = i + 1; j < intervals.length; j++) {
    if (intervals[i].start < intervals[j].end &&
        intervals[j].start < intervals[i].end) {
      intersections.push([intervals[i], intervals[j]]);
    }
  }
}

console.log(intersections); // [[{start:1, end:5}, {start:3, end:7}]]

Note: Line sweep is particularly effective for problems involving intervals or geometric objects where a vertical line can be used to process events sequentially.

2. Sorting Events

Event Type	Description	Sorting Criteria	Example
Start Event	Indicates the beginning of a line segment or interval	Left x-coordinate ascending, then y-coordinate ascending	`{x: 1, y: 2, type: 'start'}`
End Event	Indicates the end of a line segment or interval	Right x-coordinate ascending, then y-coordinate ascending	`{x: 5, y: 3, type: 'end'}`
Intersection Event	Occurs when two or more lines intersect at a point	X-coordinate ascending, then y-coordinate ascending	`{x: 3, y: 4, type: 'intersection'}`

Example: Sorting Events by X and Y Coordinates

const events = [
  { x: 1, y: 2, type: 'start' },
  { x: 5, y: 3, type: 'end' },
  { x: 3, y: 4, type: 'intersection' },
  { x: 1, y: 1, type: 'start' }
];

events.sort((a, b) => {
  if (a.x !== b.x) return a.x - b.x;
  return a.y - b.y;
});

console.log(events);
// Output:
// [
//   { x: 1, y: 1, type: 'start' },
//   { x: 1, y: 2, type: 'start' },
//   { x: 3, y: 4, type: 'intersection' },
//   { x: 5, y: 3, type: 'end' }
// ]

Note: When sorting events, prioritize x-coordinate first to process events from left to right. If x-coordinates are equal, sort by y-coordinate to handle vertical ordering correctly.

3. Solving Rectangle Area Union

The Line Sweep Algorithm is commonly used to solve the Rectangle Area Union problem, where we need to compute the total area covered by a set of axis-aligned rectangles.

Property	Description	Notes
Input	List of rectangles defined by their bottom-left and top-right coordinates.	Each rectangle is represented as `[x1, y1, x2, y2]`.
Output	Total area covered by the union of rectangles.	Overlapping regions are counted only once.
Approach	Use a sweep line moving vertically through the rectangles.	At each y-coordinate, maintain active intervals on the x-axis and compute union length.

Example: Rectangle Area Union

function rectangleAreaUnion(rectangles) {
  const events = [];
  for (const [x1, y1, x2, y2] of rectangles) {
    events.push({y: y1, type: 'start', x1, x2});
    events.push({y: y2, type: 'end', x1, x2});
  }

  events.sort((a, b) => a.y - b.y);

  let totalArea = 0;
  let prevY = 0;
  const activeIntervals = [];

  for (const event of events) {
    const currentY = event.y;
    const width = getUnionLength(activeIntervals);
    totalArea += (currentY - prevY) * width;
    prevY = currentY;

    if (event.type === 'start') {
      activeIntervals.push([event.x1, event.x2]);
    } else {
      const index = activeIntervals.findIndex(interval => interval[0] === event.x1 && interval[1] === event.x2);
      if (index !== -1) {
        activeIntervals.splice(index, 1);
      }
    }
  }

  return totalArea % (1e9 + 7);
}

function getUnionLength(intervals) {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[0] - b[0]);
  let total = 0;
  let lastStart = intervals[0][0];
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (start <= lastEnd) {
      lastEnd = Math.max(lastEnd, end);
    } else {
      total += lastEnd - lastStart;
      lastStart = start;
      lastEnd = end;
    }
  }

  total += lastEnd - lastStart;
  return total;
}

Note: The algorithm uses a sweep line that moves vertically. At each y-coordinate, it processes events (start/end of rectangles) and computes the union of active intervals on the x-axis.

Key Steps

Generate events for rectangle start and end at y-coordinates.
Sort events by y-coordinate.
Process events in order, maintaining a list of active x-intervals.
For each y-step, compute the union length of intervals and accumulate area.

4. Finding Overlapping Intervals

Event Type	Description	Usage
Start	Indicates the beginning of an interval	Insert into sweep line
End	Indicates the end of an interval	Remove from sweep line

Example: Event Processing

const intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 4 },
  { start: 5, end: 7 }
];

const events = [];

intervals.forEach(interval => {
  events.push({ time: interval.start, type: 'start' });
  events.push({ time: interval.end, type: 'end' });
});

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

console.log(events);
// Output:
// [
//   { time: 1, type: 'start' },
//   { time: 2, type: 'start' },
//   { time: 3, type: 'end' },
//   { time: 5, type: 'start' },
//   { time: 7, type: 'end' }
// ]

Example: Overlap Detection

let activeIntervals = 0;
let overlaps = [];

events.forEach(event => {
  if (event.type === 'start') {
    activeIntervals++;
    if (activeIntervals > 1) {
      overlaps.push(event.time);
    }
  } else {
    activeIntervals--;
  }
});

console.log('Overlapping times:', overlaps);
// Output:
// Overlapping times: [2, 3]

Note: The line sweep algorithm efficiently detects overlapping intervals by processing events in sorted order and maintaining a count of active intervals at each point.

5. Implementing Skyline Problem

The Skyline Problem involves determining the silhouette formed by a set of buildings when viewed from the side. This is a classic application of the line sweep algorithm.

Property	Description	Notes
Building	Each building is represented as [left, right, height]	left and right are x-coordinates; height is the building's height
Event	Events are created at building start and end points	Start event: [left, height] End event: [right, -height]
Active Heights	Set of active building heights at a given x-coordinate	Used to determine the maximum height at any point

Example: Skyline Calculation

function getSkyline(buildings) {
  const events = [];
  for (const [left, right, height] of buildings) {
    events.push([left, -height]); // Start event
    events.push([right, height]); // End event
  }
  events.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0];
    return a[1] - b[1];
  });

  const result = [];
  const activeHeights = new MaxHeap();
  let prevHeight = 0;

  for (const [x, height] of events) {
    if (height < 0) {
      activeHeights.insert(-height);
    } else {
      activeHeights.remove(height);
    }

    const currentHeight = activeHeights.isEmpty() ? 0 : activeHeights.peek();
    if (currentHeight !== prevHeight) {
      result.push([x, currentHeight]);
      prevHeight = currentHeight;
    }
  }

  return result;
}

Note: The algorithm uses a max heap to efficiently track the maximum height among active buildings at any x-coordinate.

Key Steps in Skyline Algorithm

Create events for building starts and ends
Sort events by x-coordinate, with special handling for ties
Use a max heap to maintain active building heights
Process events and update skyline when height changes

6. Solving Closest Pair of Points

The Closest Pair of Points problem involves finding the two points with the smallest Euclidean distance in a set of points. A line sweep algorithm can be used to solve this efficiently.

Step	Description	Details
1. Sort Points	Sort points by x-coordinate	Points are sorted to process them in order of increasing x-coordinate.
2. Initialize Sweep Line	Start sweeping from left to right	A vertical line moves from left to right across the plane.
3. Maintain Active Set	Keep track of points within a vertical window	Points within a distance of the current minimum are stored in an active set.
4. Check Neighbors	For each new point, check nearby points in the active set	Only points within a vertical window of size 2 * min_distance are considered.
5. Update Minimum	Update the minimum distance if a closer pair is found	The algorithm updates the global minimum as it processes each point.

Example: Closest Pair of Points Implementation

function closestPairOfPoints(points) {
  // Sort points by x-coordinate
  points.sort((a, b) => a.x - b.x);

  let minDistance = Infinity;
  let closestPair = null;

  // Sweep line approach
  const activeSet = [];

  for (let i = 0; i < points.length; i++) {
    const currentPoint = points[i];

    // Remove points that are too far to the left
    while (activeSet.length > 0 && activeSet[0].x < currentPoint.x - minDistance) {
      activeSet.shift();
    }

    // Check nearby points in the active set
    for (let j = 0; j < activeSet.length; j++) {
      const point = activeSet[j];
      const distance = Math.sqrt((currentPoint.x - point.x) ** 2 + (currentPoint.y - point.y) ** 2);
      if (distance < minDistance) {
        minDistance = distance;
        closestPair = [currentPoint, point];
      }
    }

    // Add current point to active set
    activeSet.push(currentPoint);
  }

  return { minDistance, closestPair };
}

// Example usage:
const points = [
  { x: 1, y: 2 },
  { x: 3, y: 4 },
  { x: 5, y: 6 },
  { x: 2, y: 3 }
];

const result = closestPairOfPoints(points);
console.log(result);

Note: The algorithm assumes that no two points share the same x-coordinate. If duplicates exist, additional handling is required.

7. Finding Intersecting Segments

Property	Description	Example
Segment	A line segment defined by two endpoints (x1, y1) and (x2, y2)	`{x1: 0, y1: 0, x2: 5, y2: 5}`
Intersection Point	Coordinates where two segments meet	`{x: 2.5, y: 2.5}`

Example: Basic Segment Intersection Check

function intersect(s1, s2) {
  const [x1, y1] = [s1.x1, s1.y1];
  const [x2, y2] = [s1.x2, s1.y2];
  const [x3, y3] = [s2.x1, s2.y1];
  const [x4, y4] = [s2.x2, s2.y2];

  const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
  if (denom === 0) return null; // Lines are parallel

  const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
  const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom;

  if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
    return { x: x1 + t * (x2 - x1), y: y1 + t * (y2 - y1) };
  }
  return null;
}

Note: The algorithm uses parametric form of line equations to compute intersection points efficiently.

Workflow: Detecting Intersections Using Line Sweep

Sort all segment endpoints by x-coordinate
Process events in order from left to right
Use a sweep line to maintain active segments
For each new segment, check intersections with active segments
Report all intersection points found

8. Implementing Meeting Rooms

Property	Description	Usage
start	Start time of the meeting	`09:00`
end	End time of the meeting	`10:30`

Example: Schedule Meetings

const meetings = [
  { start: '09:00', end: '10:30' },
  { start: '10:00', end: '12:00' },
  { start: '11:00', end: '13:00' }
];

function canAttendAllMeetings(meetings) {
  meetings.sort((a, b) => a.start.localeCompare(b.start));
  
  for (let i = 0; i < meetings.length - 1; i++) {
    if (meetings[i].end > meetings[i + 1].start) {
      return false;
    }
  }
  
  return true;
}

console.log(canAttendAllMeetings(meetings)); // false

Note: The line sweep algorithm helps determine if meetings overlap by sorting events and checking for intersections.

9. Solving Perfect Rectangle

Property	Description	Notes
Input	Array of rectangles represented as [x1, y1, x2, y2]	Each rectangle has bottom-left and top-right coordinates
Output	Boolean indicating if rectangles form a perfect rectangle	Must cover exactly the area of the bounding box

Example: Check Perfect Rectangle

function isRectangleCover(rectangles) {
    let minX = Infinity, minY = Infinity;
    let maxX = -Infinity, maxY = -Infinity;
    let areaSum = 0;

    const corners = new Set();

    for (const [x1, y1, x2, y2] of rectangles) {
        minX = Math.min(minX, x1);
        minY = Math.min(minY, y1);
        maxX = Math.max(maxX, x2);
        maxY = Math.max(maxY, y2);
        areaSum += (x2 - x1) * (y2 - y1);

        const cornersList = [
            [x1, y1],
            [x1, y2],
            [x2, y1],
            [x2, y2]
        ];

        for (const [x, y] of cornersList) {
            const key = `${x},${y}`;
            if (corners.has(key)) {
                corners.delete(key);
            } else {
                corners.add(key);
            }
        }
    }

    const expectedArea = (maxX - minX) * (maxY - minY);
    if (areaSum !== expectedArea) return false;

    const expectedCorners = new Set([
        `${minX},${minY}`,
        `${minX},${maxY}`,
        `${maxX},${minY}`,
        `${maxX},${maxY}`
    ]);

    return corners.size === 4 && 
           [...expectedCorners].every(c => corners.has(c));
}

// Example usage:
const rectangles = [
    [1, 1, 3, 3],
    [3, 1, 4, 2],
    [3, 2, 4, 4],
    [1, 3, 2, 4],
    [2, 3, 3, 4]
];

console.log(isRectangleCover(rectangles)); // true

Note: The algorithm uses a line sweep approach to validate that rectangles form a perfect rectangle by checking area consistency and corner occurrences.

10. Optimizing with Data Structures

Data Structure	Use Case	Time Complexity	Notes
Segment Tree	Range queries and updates	O(log n)	Good for dynamic range max/min queries
Fenwick Tree (Binary Indexed Tree)	Prefix sum queries and updates	O(log n)	Space efficient, simpler than segment tree
Balanced BST (e.g., TreeMap)	Dynamic insertion/deletion with ordering	O(log n)	Supports range queries and key-based operations
Sweep Line with Priority Queue	Event processing in sorted order	O(log n)	Efficient for handling events in chronological order

Example: Using Fenwick Tree for Range Sum Queries

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(index, delta) {
    for (let i = index; i <= this.size; i += i & -i) {
      this.tree[i] += delta;
    }
  }

  query(index) {
    let sum = 0;
    for (let i = index; i > 0; i -= i & -i) {
      sum += this.tree[i];
    }
    return sum;
  }
}

// Example usage:
const ft = new FenwickTree(10);
ft.update(3, 5); // Add 5 to index 3
console.log(ft.query(3)); // Sum from index 1 to 3

11. Handling Edge Cases

Edge Case	Description	Solution
Overlapping Events	Multiple events occur at the same time point	Sort by event type and priority to ensure consistent processing order
Empty Input	No events or intervals to process	Return empty result or handle gracefully with default values
Duplicate Intervals	Identical intervals are present in input	Use a set or hash map to deduplicate before processing
Negative Coordinates	Intervals span negative coordinate space	Ensure sorting logic handles negative numbers correctly
Large Coordinate Values	Very large coordinate values may cause overflow or performance issues	Validate input ranges and consider using long integers or big number libraries

Example: Handling Overlapping Events

const events = [
  { time: 1, type: 'start', interval: [1, 3] },
  { time: 1, type: 'end', interval: [2, 4] },
  { time: 2, type: 'start', interval: [2, 5] }
];

events.sort((a, b) => {
  if (a.time !== b.time) return a.time - b.time;
  // Prioritize 'start' over 'end' to maintain consistency
  return a.type === 'end' && b.type === 'start' ? 1 : -1;
});

console.log(events);
// Output: [
//   { time: 1, type: 'start', interval: [1, 3] },
//   { time: 1, type: 'end', interval: [2, 4] },
//   { time: 2, type: 'start', interval: [2, 5] }
// ]

Note: When handling overlapping events, always prioritize event types consistently to avoid unpredictable behavior in sweep line algorithms.