배열 내에서 겹치는 구간 찾기 (Greedy Interval Covering/Scheduling)

                                    >>> [1, 3], [3, 4], [2, 5]
여기에서 가장 겹치는 좌표는 어디인가?

1 2 3
    3 4
  2 3 4 5

이렇게 놓고 보면 3이 제일 많이 겹친다. 3을 쏘면 한번에 모두 제거가 가능하다.

여기에 구간을 추가해보자
>>> + [5, 6]
1 2 3
    3 4
  2 3 4 5
        5 6
겹치는 구간 순위 3 > 2 = 4 = 5, 총 막대 갯수 4
3을 제거하면 3개가 감소 -> 이후 5를 제거하면 1개가 감소한다.

5는 2개인데 이를 1개로 어떻게 판단하는가? -> 판단안하고 초과로 표현해도 되지 않을까?

                                    이번에는 완전 다른 구간을 하나 추가하자.
>>> + [11, 13]

1 2 3
    3 4
  2 3 4 5
        5 6
              --- 11 12 13

겹치는 구간 순위
3 > 2 = 4 = 5 > 나머지 숫자

👉 좌표중 가장 크게 겹치는 것부터 제거하는 로직은 통하지 않는다.
👉 그렇다고 가장 크게 겹치는 좌표를 무시할 수는 없다.
>>> 좌표를 선택하고 나면 해당 막대 전체 좌표를 제거 할 수 있는지?
>>> ✅되긴한데 알고리즘이 복잡한가?

                                    🔑 map(dictionary) - key: 좌표, value: listOf(구간)으로 구성

입력(targets): [listOf(구간)]

1. 가장 큰 수부터 가장 작은 수까지 key로 등록
>>> 등록시 value는 모두 빈 리스트로

2. 모든 target의 구간을 확인하여 key를 확인하고 value에 target의 idx를 기록

3. value가 가장 큰 key를 제거
>>> value에 해당하는 모든 idx를 dead에 기록
>>> value제거시 dead를 참조하도록 설정

                                    1 2 3
    3 4
  2 3 4 5
        5 6
              --- 11 12 13
target = [[1, 3], [3, 4], [2, 5], [5, 6], [11, 13]]
map = {1: [0], 2: [0,2], 3: [0, 1, 2], 4: [1, 2], 5: [2, 3], 6: [3], 7~10까지 [],
       11: [4], 12: [4], 13: [4]}

1. 가장 큰 value에 해당하는 key 제거
[0, 1, 2] -> key = 3
dead = [0, 1, 2]

2. 두번 째 큰 value에 해당하는 key 제거
>>> key: 2, 4, 5
>>> 제거시 value의 값이 dead에 속해있는지 확인
>>> 없는 value내부 값만 dead에 추가한다.

dead = [0, 1, 2, 3]
전체 갯수 = 5 dead의 길이 4
-> 다음 반복

3. 세번째로 큰 value에 해당하는 key를 제거한다.
>>> key: 1, 6, 11, 12, 13
>>> 없는 value만 추가
dead = [0, 1, 2, 3 ,4]

전체 갯수 = dead 길이 -> 끝

                                    1. 너무 원초적인 방법이라 꺼림찍하다.

2. 속도계산
>>> targets 사이즈를 n으로 두기

>>> map만드는데 소요되는 시간 O(n)
>>>
>>> target 제거에 걸리는 시간이 n(M + M -1 + M - 2 + M - 3 + ... +)의 시간 소요가 예상된다.
>>> 최악의 경우 O(n²)로 예상된다.

3. 끝이 아니다.
>>> 가령 가장 큰 수부터 제거하는 것이 틀렸다면 시간 복잡도는 더욱 증가하게 될 것 ??
>>> 겹치는게 가장 많은 순서대로 부수는게 항상 정답을 보장하는가?

                                    🤔 겹치는 부분이 가장 많은 순서대로 부수는 것이 항상 정답임을 보장하는가?

# case 1 모두 겹치지 않는 경우 -> 항상 최적

# case 2 모두 겹치는 경우 -> 항상 최적

# case 3 일부가 겹치는 경우
>>> 어떻게 막대를 그려봐도 항상 가장 많이 겹치는 부분을 부수는게 최적이다.

                                    👉 미사일 포격 위치와 부서짐의 여부는 단순히 비교로 가능하다.

ex) 좌표 1.1에서 미사일 발사한다면, 1.1이 target의 s와 e사이에 있으면 격파된다.

🤔 그렇다 해도 s와 e의 범위가 너무 크다.
예를 들어 0부터 100,000,000까지 나오면 최대 계산량은
100,000,000 * 500,000이 될 수 있다.

                                    1. e값을 기준으로 오름차순으로 정렬한다.

2. e - 0.1을 position으로 잡아서 구간 순회를 진행한다.

3. 커버가 안되는 구간이나오면 새로운 e - 0.1을 set한다.

4. 순회가 끝나면 사용된 e - 0.1의 갯수가 미사일 갯수이며 이는 최소값을 보장한다.

                                    🤔 나는 s + 0.1로 생각했는데 아니었다.
- 애초에 정렬을 생각하지 못해서 매우 복잡했다.
- 정렬을 생각했다 하고, s를 기준으로 오름차순 적용했어도 정답이 아니다.
-- s + 0.1의 경우 이후 나오는 여러 구간들을 최대한 커버할 수 없다.

ex) [3, 5], [4, 5] -> 3.1로는 1개 4.9로는 2개 커버 가능

def solution(targets):
    answer = 0

    targets.sort(key=lambda target: target[1])

    p = targets[0][1] - 0.001
    answer += 1

    for idx, target in enumerate(targets):
        if target[0] < p < target[1]:
            continue
        else:
            p = target[1] - 0.001
            answer += 1

    return answer

                                    ⌚ 시간 복잡도 분석

1. 정렬 (Tim sort) = O(NlogN)
2. target 순회 targets의 길이가 n이라고 하면, O(N)

총 O(NlogN)

                                    def solution(targets):
    answer = 0

    print(targets)
    targets.sort(key=lambda target: target[1])
    print(targets)
    while 1:
        if len(targets) == 0:
            break
        p = targets[0][1] - 0.001
        answer += 1
        print("p, answer: ", p, answer)

        dead = []
        for idx, target in enumerate(targets):
            if target[0] < p < target[1]:
                print("target[0], target[1], p", target[0], target[1], p)
                dead.append(idx)
            else:
                break

        print("dead: ", dead)
        for d in dead:
            targets.pop(d)
        print("after dead: ", targets)

                                    [[4, 5], [4, 8], [10, 14], [11, 13], [5, 12], [3, 7], [1, 4]]
[[1, 4], [4, 5], [3, 7], [4, 8], [5, 12], [11, 13], [10, 14]]

p, answer:  3.999 1
target[0], target[1], p 1 4 3.999
dead:  [0]
after dead:  [[4, 5], [3, 7], [4, 8], [5, 12], [11, 13], [10, 14]]
p, answer:  4.999 2
target[0], target[1], p 4 5 4.999
target[0], target[1], p 3 7 4.999
target[0], target[1], p 4 8 4.999
dead:  [0, 1, 2]
🤔 after dead:  [[3, 7], [5, 12], [10, 14]] -> ???
p, answer:  6.999 3
target[0], target[1], p 3 7 6.999
target[0], target[1], p 5 12 6.999
dead:  [0, 1]
after dead:  [[5, 12]]
p, answer:  11.999 4
target[0], target[1], p 5 12 11.999
dead:  [0]
after dead:  []

                                    인덱스:   0        1        2        3         4         5
         [4,5],  [3,7],  [4,8],  [5,12],   [11,13],  [10,14]

>>> pop(0)

인덱스:  0        1        2         3         4
       [3,7],  [4,8],  [5,12],   [11,13],  [10,14]

>>> pop(1)

인덱스:  0        1        2         3
       [3,7],  [5,12],  [11,13],  [10,14]

>>> pop(2)

최종: [[3,7], [5,12], [10,14]]

                                    👉
1. 대안 idx값을 저장할게 아니라 횟수를 저장 하여
pop(0)를 3번하는 것이 낫다

👉 코드를 다음과 같이 수정가능하면 안전하다.
for d in sorted(dead, reverse=True):
    targets.pop(d)

🥅 하지만 pop()을 직접 사용하는 방법은 이 문제에서 정답이 아니므로 pop()없이 코드를 작성해야한다.