JavaScript Coding Test Course, Dividing Segments into Groups

This course aims to cover “Grouping Line Segments,” which is one of the frequently asked problems in JavaScript coding tests.
This problem tests the process of finding overlapping line segments among the given segments and grouping them accordingly.
We will examine various situations and considerations that may arise while solving algorithmic problems in detail.

Problem Definition

Problem: Given an array of line segments, return the number of groups formed by overlapping line segments.

For example, let’s assume we are given the following line segments:

Line Segments: [[1, 3], [2, 4], [5, 6], [7, 10], [9, 11]]

There are two groups in this array:

• First Group: [[1, 3], [2, 4]]
• Second Group: [[5, 6], [7, 10], [9, 11]]

Approach to the Problem

To solve this problem, we can use the following approach:

1. Sorting: Sort the line segments based on their start or end points.
2. Grouping: Traverse through the sorted line segments and group overlapping segments together.

Step 1: Sorting the Line Segments

Sort the line segments based on their starting points. This makes it easier to determine when segments overlap.

Step 2: Implementing the Grouping Logic

While traversing the sorted line segments, check if the current segment overlaps with the previous one.
If they do not overlap, start a new group; if they do overlap, add the current segment to that group.

Example Code

The following JavaScript code is written based on the above logic.

function groupLines(lines) {
    // 1. Sort line segments based on starting points
    lines.sort((a, b) => a[0] - b[0]);

    let groups = [];
    let currentGroup = [];

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

        if (currentGroup.length === 0) {
            currentGroup.push(line);
        } else {
            // If the start of the current segment is less than or equal to the end of the previous segment, they overlap.
            if (line[0] <= currentGroup[currentGroup.length - 1][1]) {
                currentGroup.push(line);
            } else {
                // If they do not overlap, save the group and start a new one
                groups.push(currentGroup);
                currentGroup = [line];
            }
        }
    }

    // Add the last group
    if (currentGroup.length > 0) {
        groups.push(currentGroup);
    }

    return groups.length;
}

// Example input
const lines = [[1, 3], [2, 4], [5, 6], [7, 10], [9, 11]];
console.log(groupLines(lines));  // Output: 2

Code Explanation

The code above groups the line segments through the following processes:

1. Sorting: Sorted the array of segments in ascending order based on starting points.
2. Group Searching: Checked if the current segment overlaps with the previous one while traversing each segment.
3. Group Saving: When encountering a non-overlapping segment, saved the current group and started a new one.

Complexity Analysis

The time complexity of this algorithm is mainly determined by the sorting part. Sorting takes O(n log n), and the process of traversing the segments and grouping them takes O(n).
Therefore, the overall time complexity is O(n log n).

The space complexity is O(n) in the worst case where no segments overlap.

Conclusion

In this course, we learned how to determine and group overlapping line segments through the problem “Grouping Line Segments.”
We explored the process of effectively solving the problem using basic algorithm techniques like sorting and searching.

Such algorithm problems often appear in real coding tests, so practicing the approaches mentioned above and solving various variations is important.
We will be covering useful coding test problems in the next course as well, so stay tuned!