https://www.codewars.com/kata/52b7ed099cdc285c300001cd/cpp
이번 문제는 from-to의미의 숫자 pair를 복수개 전달해주고,
중첩되는 구간을 고려하여, interval을 구하라는 문제입니다.
{1, 4}, {2, 6}이 주어지면, 중복이 있기 때문에 {1,6}까지로 볼 수 있고, 이 때 interval은 5가 됩니다.
바로 처리할수도 있어 보이긴 했는데
머리쓰기가 귀찮아서 주어진 데이터에서 min, max를 찾아 그 길이 만큼 bool vector를 정의했습니다.
그리고 다시 주어진 데이터만큼 순회하며, interval내에 항목을 true로 업데이트 한 이후에, bool vector에서 true마킹 된 개수를 세어서 정답으로 반환했습니다.
일단 이렇게 하면 통과는 하지만, bool vector size를 잡고
그 크기만큼 순회를 한다는 점에서, 큰 숫자가 들어왔을 때에는 성능이슈가 발생하는 나쁜 해결법입니다.
다행히 그런 테스트는 안나와서 한번에 통과하긴 했네요.
int sum_intervals(std::vector<std::pair<int, int>> intervals)
{
//find max
int min = 1e+6, max = -1e+6;
for (int i = 0; i < intervals.size(); ++i)
{
if (min > intervals[i].first)
min = intervals[i].first;
if (max < intervals[i].second)
max = intervals[i].second;
}
std::vector<bool> has(max - min, false);
for (int i = 0; i < intervals.size(); ++i)
{
for (int s = intervals[i].first; s < intervals[i].second; ++s)
{
has[s - min] = true;
}
}
int ret = 0;
for (int i = 0; i < max - min; ++i)
{
if (has[i])
++ret;
}
return ret;
}