阿祁的部落格

ZeroJudge b526- 先別管這個了，你聽過微鼓勵嗎？解題心得( 題目 )

解題概念:PriortyQueue(優先佇列) (感謝jam930725@gmail.com(浮沉沉沉沉沉沉沉沉)解釋方法，講得很詳細)

解題方法:我們不可能一個一個人討論，我們必須得討論這些區間的疊加情形，一次從依照起點排序的PriortyQueue取出兩個區間s1、s2，如果不重疊，則結算s1，然後把s2放回去；如果有重疊，結算前面沒重疊的，中間的效果則被抵銷，後面沒重疊的再放回去，最後輸出總人數減鰾蹲下的。

參考程式碼( 如果有更好意見可在下方留言，以做為本文章之補充，感謝! ):

import java.io.*;
import java.util.*;
public class zjb526 {
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static int ret,r;
	public static void main(String[] args) throws Exception{
		final int n=readnum();
		final int m=readnum();
		PriorityQueue<seg> pq=new PriorityQueue<>(new Comparator<seg>() {
			public int compare(seg f,seg s) {//實作Comparator
				if(f.b>s.b) {
					return 1;
				}
				else if(f.b<s.b) {
					return -1;
				}
				else if(f.e>s.e) {
					return 1;
				}
				else {
					return -1;
				}
			}
		});
		for(int i=0;i<m;i++) {
			pq.offer(new seg(readnum(),readnum()));
		}
		long r=0;
		seg s1,s2;
		while(pq.size()>1) {
			s1=pq.poll();
			s2=pq.poll();
			if(s1.e<s2.b) {
				r+=s1.e-s1.b+1;
				pq.offer(s2);
			}
			else if(s1.e>=s2.e){
				r+=s2.b-s1.b;
				if(s1.e!=s2.e)pq.offer(new seg(s2.e+1,s1.e));
			}
			else {
				r+=s2.b-s1.b;
				pq.offer(new seg(s1.e+1,s2.e));
			}
		}
		if(pq.size()==1) { 
			s1=pq.poll();
			System.out.println(n-(r+s1.e-s1.b+1));
		}
		else {
			System.out.println(n-r);
		}
		
	}
	public static int readnum() throws Exception {//輸入
		ret=0;
		r=br.read();
		while(r>47&&r<58) {
			ret*=10;
			r-=48;
			ret+=r;
			r=br.read();
		}
		return ret;
	}
}

class seg{//定義區間物件
	int b,e;
	seg(int x,int y) {
		b=x;
		e=y;
	}
}