코딩테스트 문제 (4) - 구간 병합

이 문제는 구간들을 원소로 가진 입력 리스트에 대해 겹치는 구간을 병합한 결과를 제출하는 문제입니다.

문제

1. [[2,6],[15,18],[1,3],[8,10]] 
=> [[1,6],[8,10],[15,18]]

입력은 정렬되지 않은 상태로 들어옵니다.

풀이

먼저 입력이 정렬되지 않았으니 시작점 기준으로 정렬해야 할 것 같습니다. 그 후, for 루프를 통해 각 구간을 순회하면서 전 구간의 끝점과 현 구간의 시작점을 비교해서 두 값이 겹치게 되면 병합하면 될 것 같습니다.

kaggle.com 의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 난이도: 하

참조

• <파이썬 알고리즘 인터뷰>, p497-498
• leetcode.com/problems/merge-intervals/