테이블 옮기기 [백준 7348][JAVA][실버3][그리디]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/7348

7348번: 테이블 옮기기

회의실 배정과 유사한 문제

같은 복도를 공유하는 시간대가 있으면 최소작업시간이 늘어난다.

같은 시간을 공유할 수 있는(겹치지 않는) 작업끼리 모아서 해결한다.

package Study0319;

import java.io.FileInputStream;
import java.util.*;

public class 테이블옮기기 {

	public static class Table implements Comparable<Table> {
		int s;
		int t;
		int l;

		public Table(int s, int t) {
			if (s < t) {
				this.s = s;
				this.t = t;
			} else {
				this.s = t;
				this.t = s;
			}
			this.l = Math.abs(s - t);
		}

		@Override
		public int compareTo(Table o) {
			if (s == o.s)
				return Integer.compare(l, o.l);
			return Integer.compare(s, o.s);
		}
	};

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = sc.nextInt();
		int s, t;
		List<Table> list = new ArrayList<>();
		for (int tc = 0; tc < T; tc++) {
			int N = sc.nextInt();
			for (int i = 0; i < N; i++) {
				s = (sc.nextInt()-1)/2;
				t = (sc.nextInt()-1)/2;
				list.add(new Table(s, t));
			}

			int ans = 0;
			Collections.sort(list);
			while (!list.isEmpty()) {
				t = Integer.MIN_VALUE;
				ans+=10;
				List<Table> tmp = new ArrayList<>();
				for (int i = 0; i < list.size(); i++) {
					if (list.get(i).s > t) {
							t = list.get(i).t;
					}else {
						tmp.add(list.get(i));
					}
				}
				list = tmp;
			}
			System.out.println(ans);
		}
	}
}