Java Coding Test Course, Grouping Line Segments

Hello! In this coding test lecture, we are dealing with the problem of dividing given line segments into groups. This problem is one of the common questions in various programming languages, particularly requiring the ability to determine whether line segments overlap and to group them efficiently based on this.

Problem Description

When there is a list of given line segments, segments that have overlapping parts must be combined into the same group. A line segment is represented by two coordinates (x1, x2), where x1 is always less than x2. Each line segment is given in the form of [x1, x2].

Problem Definition

Define a function:

public int groupLineSegments(int[][] segments)

Input

  • Number of line segments: n (1 ≤ n ≤ 100,000)
  • segments: A 2D array representing the line segments (the starting and ending points of each segment)

Output

  • Number of groups of overlapping line segments

Example

Input: [[1,3], [2,4], [5,6], [8,10], [9,12]]
Output: 3
Explanation: [[1,3], [2,4]] is the first group, [[5,6]] is the second group, and [[8,10], [9,12]] is the third group.

Problem Solving Process

To solve this problem, it is necessary to determine the overlaps of the line segments and form groups based on this. We can use the following algorithm.

Algorithm Steps

  • 1. Sort the line segments based on the starting point.
  • 2. Check the starting and ending points to divide into groups.
  • 3. If the end point of each group is greater than or equal to the starting point of the next group, combine them into the same group.

Implementation

Let’s implement this algorithm in Java.

import java.util.Arrays;

public class LineSegmentGrouping {
    
    public int groupLineSegments(int[][] segments) {
        // Sort the segments by the starting point
        Arrays.sort(segments, (a, b) -> Integer.compare(a[0], b[0]));
        int groupCount = 0;
        int currentEnd = Integer.MIN_VALUE;

        for (int[] segment : segments) {
            if (segment[0] > currentEnd) {
                // Start a new group
                groupCount++;
                currentEnd = segment[1];
            } else {
                // Update the end point of the group
                currentEnd = Math.max(currentEnd, segment[1]);
            }
        }

        return groupCount;
    }
    
    public static void main(String[] args) {
        LineSegmentGrouping lsg = new LineSegmentGrouping();
        int[][] segments = {{1, 3}, {2, 4}, {5, 6}, {8, 10}, {9, 12}};
        System.out.println("Number of groups: " + lsg.groupLineSegments(segments)); // 3
    }
}

Code Explanation

The above code presents a simple yet efficient way to divide line segments into groups.

  • Sorting: In the first line, Arrays.sort is used to sort the segments in ascending order based on the starting point. This makes it easier to judge overlapping segments.
  • Group Count: The groupCount variable counts the number of groups, while currentEnd remembers the maximum end point of the current group.
  • Condition Check: Each segment is checked to decide whether to start a new group or update the end point of the current group.

Time Complexity

The time complexity of this solution is O(n log n). Sorting the segments takes O(n log n) time, while the loop for grouping takes O(n). Therefore, the overall time complexity is O(n log n).

Conclusion

The problem of dividing line segments into groups requires the ability to judge overlapping intervals and has various applications. I hope this lecture helps you improve your algorithm problem-solving skills and Java coding abilities.