[BOJ 1911] 흙길 보수하기

[sh0723]

Problem

비가 온 뒤 생긴 물웅덩이들을 길이가 L인 널빤지로 덮어야 한다. 각 웅덩이는 시작 위치와 끝 위치로 주어지고, 널빤지는 정수 위치에 놓을 수 있으며 길이 L만큼 연속한 구간을 덮는다. 모든 물웅덩이를 덮기 위해 필요한 널빤지의 최소 개수를 구한다.

Input

• 첫째 줄에 물웅덩이의 개수 N과 널빤지의 길이 L이 주어진다.
• 다음 N개의 줄에는 각 물웅덩이의 시작 위치와 끝 위치가 주어진다.
• 물웅덩이의 구간은 시작 위치 이상, 끝 위치 미만으로 본다.
• 1 <= N <= 10000, 1 <= L <= 1000000000

Output

• 모든 물웅덩이를 덮기 위해 필요한 널빤지의 최소 개수를 출력한다.

Sample

3 3
1 6
13 17
8 12

5

Solution Path

• src/week5/BOJ1911/BOJ1911_V1.cpp