LeetCode-上書きされた区間を削除
タイトル
区間リストをあげます.他の区間で上書きされた区間を削除してください.c<=a,b<=dの場合にのみ、区間[a,b)が区間[c,d)で上書きされていると考えられます.すべての削除操作が完了したら、リスト内の残りの区間の数を返してください.
例
入力:intervals=[[1,4],[3,6],[2,8]]出力:2解釈:区間[3,6]は区間[2,8]で上書きされたので削除された.
ヒント: 1 <= intervals.length <= 1000 0 <= intervals[i][0] < intervals[i][1] <= 10^5 はすべてのiに対して!=j:intervals[i] != intervals[j]
解法1(暴力捜索):
考え方:1.1行あたりの循環数、デフォルトは0です.2.含まれるか否かを順次判断する.3.含まれていない場合は1をカウントし、そうでない場合は次のループを実行します.4.カウントコードを返します.
解法2(線形スキャン):
考え方:1.配列の最初の数値を並べ替えます.最初の数値が同じ場合、2番目の数値に基づいて並べ替えられます.デフォルトのカウントは0 2です.既定の基点を{-1,-1}に設定(題目は配列の数値範囲が0より大きい)3.ループ項の区間の末尾が基点の末尾より小さい場合.ループ項が上書きされて次のループがループされることを示す.4.ループ項の末尾が基点の末尾より大きい場合,基点とループ項の始点が一致するか否かを判断し,一致する場合はループ項を基点にするが,現在のループ項には基点が含まれているためカウントを追加することはできない点ですが、基点とカウントが増えました.そうでない場合は、ループ項目が囲まれていないことを示し、基点を現在のループ項目に変更し、カウントを1加算.5.戻りカウントは、空き領域数コードです.
区間リストをあげます.他の区間で上書きされた区間を削除してください.c<=a,b<=dの場合にのみ、区間[a,b)が区間[c,d)で上書きされていると考えられます.すべての削除操作が完了したら、リスト内の残りの区間の数を返してください.
例
入力:intervals=[[1,4],[3,6],[2,8]]出力:2解釈:区間[3,6]は区間[2,8]で上書きされたので削除された.
ヒント:
解法1(暴力捜索):
考え方:1.1行あたりの循環数、デフォルトは0です.2.含まれるか否かを順次判断する.3.含まれていない場合は1をカウントし、そうでない場合は次のループを実行します.4.カウントコードを返します.
public int RemoveCoveredIntervals(int[][] intervals)
{
int count = 0;
for (int i = 0; i < intervals.Length; i++)
{
bool isContain = false;
for (int j = 0; j < intervals.Length; j++)
{
if (i != j && intervals[i][0] >= intervals[j][0] && intervals[i][1] <= intervals[j][1])
{
isContain = true;
break;
}
}
count += isContain ? 1 : 0;
}
return count;
}
解法2(線形スキャン):
考え方:1.配列の最初の数値を並べ替えます.最初の数値が同じ場合、2番目の数値に基づいて並べ替えられます.デフォルトのカウントは0 2です.既定の基点を{-1,-1}に設定(題目は配列の数値範囲が0より大きい)3.ループ項の区間の末尾が基点の末尾より小さい場合.ループ項が上書きされて次のループがループされることを示す.4.ループ項の末尾が基点の末尾より大きい場合,基点とループ項の始点が一致するか否かを判断し,一致する場合はループ項を基点にするが,現在のループ項には基点が含まれているためカウントを追加することはできない点ですが、基点とカウントが増えました.そうでない場合は、ループ項目が囲まれていないことを示し、基点を現在のループ項目に変更し、カウントを1加算.5.戻りカウントは、空き領域数コードです.
public int RemoveCoveredIntervals(int[][] intervals)
{
int count = 0;
Array.Sort(intervals, (a, b) => a[0] > b[0] || (a[0] == b[0] && a[1] > b[1]) ? 1 : -1);
int[] tem = {
-1, -1 };
for (int i = 0; i < intervals.Length; i++)
{
if (tem[1] < intervals[i][1])
{
if (tem[0] != intervals[i][0])
{
count++;
}
tem[0] = intervals[i][0];
tem[1] = intervals[i][1];
}
}
return count;
}