시간초과와 메모리초과로 고생한 문제다. 범위가 무려 100,000,000 이어서 일반적인 생각으로는 풀 수 없었다.(ㅠㅠ)
같은 스터디원의 기발한 아이디어로 입력된 unique한 수만 list에 저장한 후, 인덱스 값을 이용하여 답을 구했다.
비슷한 코드인데 자꾸 시간초과가 나서 보니까 정말 어이없게도 LinkedList를 ArrayList로 바꾸니까 해결되었다. 해당 문제에서는 순차적인 삽입과 접근만 일어나서 그런거같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main_2370 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
int[] left = new int[N];
int[] right = new int[N];
int l, r;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
left[i] = Integer.parseInt(st.nextToken());
right[i] = Integer.parseInt(st.nextToken());
if(!list.contains(left[i])) list.add(left[i]);
if(!list.contains(right[i])) list.add(right[i]);
}
Collections.sort(list);
int[] res = new int[list.size()];
for (int i = 0; i < N; i++) {
l = list.indexOf(left[i]);
r = list.indexOf(right[i]);
for (int j = l; j <= r; j++) res[j] = i;
}
Set<Integer> set = new HashSet<>();
for (int i = 0, end = list.size(); i < end; i++) set.add(res[i]);
System.out.println(set.size());
}
}