Untitled

#include <stdio.h>
#include <string.h>
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)

int left[5005], right[5005];
int wall[5005]; //record how many soldiers guard each wall

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        memset(wall, 0, sizeof(wall));
        
        int n, q, guarded_len = 0, ans = 0;
        scanf("%d%d", &n, &q);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d", &left[i], &right[i]);

            // count how many people can guard the i-th wall
            // count the maximum length of the wall guarded
            for(int j=left[i];j<=right[i];j++)
            {
                if(wall[j]==0) guarded_len++;
                wall[j]++;
            }
        }

        // 任選兩個soldier移除，看哪一種結果最好
        for (int i=0;i<q-1;i++) {
            for (int j=i+1;j<q;j++) {

                // prevent from modifying len
                int tmp_len = guarded_len;

                // Case 1: without overlap
                if (right[i] < left[j] || right[j] < left[i]) {
                    for (int idx = left[i]; idx <= right[i]; idx++) {
                        if (tmp_len <= ans) break;
                        if (wall[idx]==1) tmp_len--; //if there is only 1 soldier guarding
                    }
                    for (int idx = left[j]; idx <= right[j]; idx++) {
                        if (tmp_len <= ans) break;
                        if (wall[idx]==1) tmp_len--;
                    }
                }

                // Case 2: with overlap
                else {
                    int l_M, l_m, r_M, r_m;
                    l_M = max(left[i], left[j]);
                    l_m = min(left[i], left[j]);
                    r_M = max(right[i], right[j]);
                    r_m = min(right[i], right[j]);
                    for (int idx = l_m; idx <= r_M; idx++) {
                        if (tmp_len <= ans) break;
                        // if the overlap part has only two soldiers guarding
                        if (idx >= l_M && idx <= r_m && wall[idx]==2) tmp_len--;
                        // if the non-overlap part has only one soldier guarding
                        if ((idx < l_M || idx > r_m) && wall[idx]==1) tmp_len--;
                    }
                }
                // get the maximum tmp_len
                ans = ans > tmp_len ? ans : tmp_len;
            }
        }
        printf("%d\n", ans);
    }
}