【AtCoder Beginner Contest 127】 C - Prisonを解いてみた

C - Prison

AtCoder Beginner Contest 127の C - Prisonを解いてみました。
最初に提出したコードが以下なのですが、「TLE」が出てしまい失敗。。

TLE (Time Limit Exceeded)とは
問題で指定された実行時間以内にプログラムが終了せず失敗すること。

#include <iostream>

using namespace std;

int main()
{
   int n, m;
   cin >> n >> m;

   int numStart[m];
   int numEnd[m];
   for (int i = 0; i < m; i++)
   {
       cin >> numStart[i] >> numEnd[i];
   }
   
   int sum = 0;
   for (int idNum = 1; idNum <= n; idNum++)
   {
       bool isInclude = true;
       for (int gateNum = 0; gateNum < m; gateNum++)
       {
           if (idNum < numStart[gateNum] || numEnd[gateNum] < idNum)
           {
               isInclude = false;
               break;
           }
       }
       
       if (isInclude)
       {
           sum++;
       } 
   }

   cout << sum << endl;
   
   return 0;
}

上記では下記のようにforを入れ子にしているため、
計算量オーダーがO(n2)になっています。
「TLE」が出ているのはここが原因だなと踏みました。

forをなんとか1回分に収めて計算量をO(n)にしようと模索してたら、
ふと解法をひらめきました！

上記を踏まえて問題を解くとforを1回分に収めることができ、
無事TLEにならずに問題をパスしました！

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
   int n, m;
   cin >> n >> m;

   int numStart[m];
   int numEnd[m];
   for (int i = 0; i < m; i++)
   {
       cin >> numStart[i] >> numEnd[i];
   }
   
   int startMaxNum = numStart[0];
   int endMinNum = numEnd[0];
   for (int gateIndex = 0; gateIndex < m; gateIndex++)
   {
       if (numStart[gateIndex] > startMaxNum)
       {
           startMaxNum = numStart[gateIndex];
       }

       if (numEnd[gateIndex] < endMinNum)
       {
           endMinNum = numEnd[gateIndex];
       }
   }

   int result = max(0, (endMinNum - startMaxNum + 1));

   cout << result << endl;
   
   return 0;
}

コーディングスキルはまだまだ拙いので、これからもAtCoderの問題を解いていこうと思います。