\n This course aims to cover “Grouping Line Segments,” which is one of the frequently asked problems in JavaScript coding tests.
\n This problem tests the process of finding overlapping line segments among the given segments and grouping them accordingly.
\n We will examine various situations and considerations that may arise while solving algorithmic problems in detail.\n<\/p>\n
\nProblem:<\/strong> Given an array of line segments, return the number of groups formed by overlapping line segments.\n<\/p>\n \n For example, let’s assume we are given the following line segments:\n<\/p>\n \n There are two groups in this array:<\/p>\n To solve this problem, we can use the following approach:<\/p>\n \n Sort the line segments based on their starting points. This makes it easier to determine when segments overlap.\n<\/p>\n \n While traversing the sorted line segments, check if the current segment overlaps with the previous one. \n The following JavaScript code is written based on the above logic.\n<\/p>\n \n The code above groups the line segments through the following processes:\n<\/p>\n \n 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). \n The space complexity is O(n) in the worst case where no segments overlap.\n<\/p>\n \n In this course, we learned how to determine and group overlapping line segments through the problem “Grouping Line Segments.” \n Such algorithm problems often appear in real coding tests, so practicing the approaches mentioned above and solving various variations is important. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\nLine Segments: [[1, 3], [2, 4], [5, 6], [7, 10], [9, 11]]\n<\/code><\/pre>\n\n
Approach to the Problem<\/h2>\n
\n
Step 1: Sorting the Line Segments<\/h3>\n
Step 2: Implementing the Grouping Logic<\/h3>\n
\n If they do not overlap, start a new group; if they do overlap, add the current segment to that group.\n<\/p>\nExample Code<\/h2>\n
\nfunction groupLines(lines) {\n \/\/ 1. Sort line segments based on starting points\n lines.sort((a, b) => a[0] - b[0]);\n\n let groups = [];\n let currentGroup = [];\n\n for (let i = 0; i < lines.length; i++) {\n const line = lines[i];\n\n if (currentGroup.length === 0) {\n currentGroup.push(line);\n } else {\n \/\/ If the start of the current segment is less than or equal to the end of the previous segment, they overlap.\n if (line[0] <= currentGroup[currentGroup.length - 1][1]) {\n currentGroup.push(line);\n } else {\n \/\/ If they do not overlap, save the group and start a new one\n groups.push(currentGroup);\n currentGroup = [line];\n }\n }\n }\n\n \/\/ Add the last group\n if (currentGroup.length > 0) {\n groups.push(currentGroup);\n }\n\n return groups.length;\n}\n\n\/\/ Example input\nconst lines = [[1, 3], [2, 4], [5, 6], [7, 10], [9, 11]];\nconsole.log(groupLines(lines)); \/\/ Output: 2\n<\/code><\/pre>\nCode Explanation<\/h2>\n
\n
Complexity Analysis<\/h2>\n
\n Therefore, the overall time complexity is O(n log n).\n<\/p>\nConclusion<\/h2>\n
\n We explored the process of effectively solving the problem using basic algorithm techniques like sorting and searching.\n<\/p>\n
\n We will be covering useful coding test problems in the next course as well, so stay tuned!\n<\/p>\n