Sum of Interval (4kyu)

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;
}