値のペアが範囲

Question

の配列の範囲の間にあるかどうかを確認、値のペアがあると言うことができます5と10の両方が4と12の間にあるので、{（6,10）、（5,7）、（6,9）、（4,12）}

この場合、Trueを返すべきです。

これは、それぞれのペアを反復処理することによって、O(N)の非常に簡単な解決策ですが、Rの値のペアの最初の値に基づいて範囲Rをソートすることでさらに改善できます（ソートでは最悪の場合O n log n））。しかし、問題は、複数の値のペアに対する答えを見つける必要があるときです。私はおそらくmapを何らかの方法で使用して、いくつかの値を再計算する必要性を減らす、より良い解決策を探しています。基本的には、動的プログラミングを使用するアプローチはありますか？

アイデア？しかし、コードも高く評価されます：P

Answer 1

マップを使用する場合は、地図のマップを最小1つと最大1つ作成することです。これにはいくつかの前処理時間がかかりますが、コストが長期間にわたり多くのルックアップを使って償却されるため、全体的に速くなります。

あなたは基本的にすべての有効な最小のキーを持つマップを作成している、とそれぞれ値そのmimumumごとに有効な最大のキーを持つマップ..例えば

（用心、内部テストされていないバック・オブ封筒コード）：！

// Psuedo-ish C++11 

typedef std::map<int, std::vector<R>> MaxMap; 
typedef std::map<int, MaxMap> MinMap; 

MinMap minMap; 

// Build maps 
for(range : R) 
{ 
    for(int i=range.min; i<=range.max; ++i) 
    { 
     MaxMap& maxMap = minMap[i]; 
     for(int j=range.min; j<=range.max; ++j) 
     { 
      // We just need some value in the map, 
      // so might as well store a list of the original ranges.. 
      mapMap[j].push_back(range); 
     } 
    } 
} 

が次に検索に、あなたの分の値を取り、MinMapでそれを見て、その後、MaxMapであなたの最大値を調べます。もちろん、

bool isValidRange(int min, int max) 
{ 
    MinMap::iterator minIt = minMap.find(min); 
    if(minIt == minMap.end()) 
    { 
     return false; 
    } 
    MaxMap& maxMap = minIt->second; 
    MaxMap::iterator maxIt = maxMap.find(max); 
    if(maxIt == maxMap.end()) 
    { 
     return false; 
    } 

    return true; 
} 

... MinMapは、任意の最小のためにあなたのすべての有効な最大値を与え、あなたの最大値が与えられた最小の有効な最大値である場合、MaxMapであなたの検索があなたに伝え、これだけを覚えておいてください自然数のために働く。あなたの範囲でネガや真実が必要な場合は、別のものが必要です...