병렬로 실행되는 최대 작업 양?

Question

문제 :

우리는 각각의 정수 시간과 종료 시간을 시작 가지고, n 개의 작업 집합이 제공됩니다. 주어진 시간에 에서 병렬로 실행되는 최대 작업 수는 얼마입니까?

알고리즘은 O (n log n) 시간으로 실행되어야합니다. 내가 직접 대답을 필요로하지 않지만 어떤 코드 조각이만큼 그들은 Java 또는 스칼라에로 환영 있도록

이

는 학교 과제입니다 (스칼라로 작성하기로 할당.)

일부 힌트의 나는 우선 순위 대기열을 활용해야한다고. 설명서를 읽었지만 실제로 사용하는 방법에 대해서는 확신 할 수 없으므로 모든 코드 스 니펫을 환영합니다.

입력 데이터는 예를 들어 Array[Pair[Int,Int]] = Array((1000,2000),(1500,2200)) 일 수 있습니다.

우선 순위 대기열의 순서를 설정하는 데 정말로 고심하고 있습니다. 그렇게하지 않으면 다른 사람이 저를 도울 수 있기를 바랍니다.

추 신 : 우선 순위 큐는 PriorityQueue() (ord)로 초기화되어야합니다.

편집 : 우선 순위 대기열을 사용하는 해결책을 생각해 냈지만 모든 답변에 대해 감사드립니다. 너희들이 내가 논리를 알아내는 것을 도왔다!

Answer 1

우선 순위 대기열을 사용하지 않고 Soln.

[(1,2), (1,5), (2,4), ....] // (a,b) : (start_time, end_time) 

단계 1 : start_time과 함께 end_time을 고려하여 배열 구조를 다음과 같이

태스크들의 어레이를 고려한다.

[1,2,1,5,2,4....] 

2 단계 : 유지 다른 배열 인덱스의 시간 내가 START_TIME인지 알고 또는 END_TIME

[S,E,S,E,S,E...] // S:Start_Time, E:End_Time 

3 단계 : 첫 번째 배열을 정렬한다. 그에 따라 다른 배열의 인덱스를 변경해야합니다.

단계 4 : 두 변수, parallel_ryt_now 및 max_parallel_till_now을 유지 관리하십시오. 다음과 같이 그리고 두 번째 배열을 통과 :

는

for i in 1:len(second_array): 
    if(second_array[i] == "S"): 
     parallel_ryt_now ++ 
    else 
     parallel_ryt_now -- 
    if parallel_ryt_now > max_parallel_till_now: 
      max_parallel_till_now = parallel_ryt_now 

논리 :

u는 start_time가 발생할 때 정렬 된 배열을 통과하는 동안, 즉 작업이 시작되었다는 의미입니다.따라서 parallel_ryt_now을 증가시키고 end_time이 발생하면 작업이 완료됨을 의미하므로 parallel_ryt_now을 감소시킵니다.

이렇게하면 매번 parallel_ryt_now var에 병렬 실행 작업이 저장됩니다.

시간 복잡성 = 정렬 + 트래버스 = O(nlogn) + O(n) = O(nlogn)

공간 복잡성 = O(n) (인덱스 i에서인지 시간에 대한 정보를 추가 배열을 저장하려면 start_time 또는 end_time입니다)

I 도움이되기를 바랍니다.