Toivoa 님께서 올려주신 에디토리얼에 덧붙여, O(n^2)의 쉬운 풀이를 제시해 봅니다. 이 문제에 알려진 더 좋은 풀이가 존재하긴 하는데, 제가 남들에게 설명할 만큼 충분히 이해하고 있지는 않은 것 같습니다.
사실 이 문제를 O(n^2)에 푼다고 하면 정말 간단해집니다.
직사각형의 밑변이 [i,j] 까지의 구간을 포함해야 한다고 칩시다. 이 때의 직사각형의 밑변의 길이는 (j - i + 1) 이고, 높이는 ( min(end[k] where k in [i, j]) - max(start[k] where k in [i, j]) ) 인 직사각형이 그러한 것들 중 최대가 될 것입니다.
그래서 O(n²⁾ 루프를 통하여 i, j를 반복합니다. 윗 부분의 높이 중 최소값과 아랫 부분의 높이 중 최대값은 j가 반복되면서 차례로 갱신할 수 있습니다. 다시 말하면, min(end[k] where k in [i, j + 1]) = min( min(end[k] where k in [i, j]), end[j + 1]) 과 같이 설명할 수 있지요.
~~~ cpp

#include
int st[2001];
int ed[2001];
int main()
{
int t;
scanf("%d", &t);
for (;t;t--)
{
int N;
scanf("%d", &N);
int i;
for (i = 0;i < N;i++)
scanf("%d %d", &st[i], &ed[i]);
int j;
int st_max, ed_min;
int ans = 0;
for (i = 0;i < N;i++)
{
st_max = 0x80000000;
ed_min = 0x7FFFFFFF;
for (j = i;j < N;j++)
{
if (st_max < st[j])
st_max = st[j];
if (ed_min > ed[j])
ed_min = ed[j];
if (st_max <= ed_min && ans < (ed_min - st_max) * (j - i + 1))
ans = (ed_min - st_max) * (j - i + 1);
}
}
printf("%d", ans);
if (t != 1)
printf("\n");
}
return 0;
}

* 그나저나 세터님은 왜 안쓰시고..
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/50376">원문보기</a>]</div>