Kotlin coding test course, grouping line segments

Problem Description

Given a set of line segments, the task is to divide the segments into groups such that no two segments in the same group overlap.
Each segment is defined by its starting point and endpoint. If there is an overlapping part between segments, they must belong to the same group,
while segments that do not overlap must belong to different groups.

Input

  • The first line contains the number of segments N (1 ≤ N ≤ 100,000).
  • From the second line onwards, N lines are provided with the starting point l and endpoint r of each segment (l <= r).

Output

Print the total number of groups needed.

Example Input

        5
        1 3
        2 5
        6 8
        7 10
        11 15

Example Output

        3

Description

Looking at the given segments, the first and second segments overlap and thus belong to the same group.
The third and fourth segments also overlap, so they belong to the same group,
while the last segment belongs to a different group, resulting in a total of 3 groups.

Solution Method

To solve this problem, a correct approach is to sort the segments first,
then sequentially compare overlapping segments to form groups.
The problem can be solved in the following steps.

Step 1: Input

Input the segments as a list. Since each segment is a pair,
we will use the Pair class to store the segments.

Step 2: Sort Segments

The criteria for sorting the segments is their starting point.
Sort in ascending order of starting points, and if starting points are the same, sort by the shorter endpoint first.

Step 3: Grouping

Traverse the sorted list and check if the current segment overlaps with the last segment in the current group.
If they overlap, they belong to the same group; if they do not overlap, start a new group.

Step 4: Output Result

Finally, count and print the number of groups.

Code Example (Kotlin)

        data class Segment(val start: Int, val end: Int)

        fun countGroups(segments: List): Int {
            val sortedSegments = segments.sortedWith(compareBy({ it.start }, { it.end }))
            var groupCount = 0
            var maxEnd = -1

            for (segment in sortedSegments) {
                if (segment.start > maxEnd) {
                    groupCount++
                    maxEnd = segment.end
                } else {
                    maxEnd = maxOf(maxEnd, segment.end)
                }
            }
            return groupCount
        }

        fun main() {
            val n = readLine()!!.toInt()
            val segments = List(n) {
                val (l, r) = readLine()!!.split(" ").map { it.toInt() }
                Segment(l, r)
            }
            println(countGroups(segments))
        }

Conclusion

Through this problem, we learned how to solve the line segment grouping issue.
We can effectively determine the number of groups using sorting and list traversal.
The code structure written in Kotlin shows high reusability and clarity,
confirming its suitability for this type of problem.
Since line segment problems frequently appear in coding tests,
it is advisable to practice similar problems.