搜索陣列兩次

-1

這是一個黑客問題。找出可以觀看的最大電影。假設列表是不同的電影。搜索陣列兩次

輸入： movieStart [] = {} 10,12,9,14,16,14

movieEnd [] = {} 11,13,15,16,18,18

輸出：4（10-11,12-13,14-16,16-18）

下面的代碼是給我正確的輸出。想知道爲這個問題可能的最佳解決方案。還有什麼算法用來解決這類問題？

static int getMaxMovies(int[] movie_start, int[] movie_end) { 

    int cnt = 0; 

    for (int i = 0; i < movie_start.length; i++) { 

     for (int j = 0; j < movie_start.length; j++) { 

      if (movie_start[j] == movie_start[i] && movie_end[j] == movie_end[i]) { 
       continue; 
      } 

      if (movie_start[j] >= movie_start[i] && movie_end[j] <= movie_end[i]) { 
       cnt += 1; 
       break; 
      } 
     } 
    } 
    return movie_start.length - cnt; 

}

來源

2014-08-29 Varun Paprunia

請問這個問題有一個網址？ – 2014-08-29 14:28:52

這不是C - 代碼示例包含數組上的'.length'屬性，這是什麼語言？ – 2015-01-21 21:31:34

@AaronMcDaid java – 2015-12-03 16:13:17

這是「活動選擇」的問題 - 這可能與O(n)可以輕鬆解決（在排序輸入的情況下）或O(nlogn)（輸入時不排序）貪心算法。如果輸入已按整理（結束）時間排序，則應選擇與先前選定的電影不衝突的電影。

僞代碼：

Sort by finish times 

int previouslySelectedIndex = 0; 
int watchedMoviesCount = 1; 

for (int i=1; i<movie_end.Length; i++) 
{ 
    if (movie_start[i] >= movie_end[previouslySelectedIndex) 
    { 
     watchedMoviesCount++; 
     previouslySelectedIndex=i; 
    } 
}

來源

2014-08-29 14:38:13 fex

搜索陣列兩次

回答

相關問題