Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.math.*;
- public class Main {
- static StringBuffer str=new StringBuffer();
- static BufferedReader bf;
- static PrintWriter pw;
- static int n;
- static List<Task> tasks;
- static class Task{
- int start, end, time;
- Task(int start, int end, int time){
- this.start=start;
- this.end=end;
- this.time=time;
- }
- public String toString(){
- return this.start+" "+this.end+" "+this.time;
- }
- }
- // implementation based on idea: https://codeforces.com/blog/entry/108625?#comment-969002
- static void solve(int te) throws Exception{
- Collections.sort(tasks, (p, q) -> p.start-q.start);
- PriorityQueue<Task> pq=new PriorityQueue<>((p, q) -> {
- return ((p.end-p.start+1)-p.time)-((q.end-q.start+1)-q.time);
- });
- long ans=0;
- int globalStart=1;
- for(int i=0;i<n;i++){
- Task cur=tasks.get(i);
- if(!pq.isEmpty()){
- Task top=pq.remove();
- int start=Math.max(top.start, cur.start);
- int end=Math.min(top.end, cur.end);
- int overLap=Math.min(end-start+1, Math.min(top.time, cur.time));
- // System.out.println(top+" -> "+cur+" -> "+ans);
- top.time-=overLap;
- cur.time-=overLap;
- ans+=overLap;
- globalStart=Math.max(globalStart, end+1);
- if(top.time>0){
- top.start=end+1;
- pq.add(top);
- }
- if(cur.time>0){
- cur.start=end+1;
- pq.add(cur);
- }
- }else{
- if(cur.start<globalStart){
- cur.time-=Math.min(globalStart-cur.start, cur.time);
- if(cur.time>0){
- cur.start=globalStart;
- pq.add(cur);
- }
- }else pq.add(cur);
- }
- }
- while(!pq.isEmpty()) ans+=pq.remove().time;
- str.append(ans).append("\n");
- }
- public static void main(String[] args) throws java.lang.Exception {
- boolean lenv=true;
- int te=1;
- if(lenv){
- bf = new BufferedReader(
- new FileReader("input.txt"));
- pw=new PrintWriter(new
- BufferedWriter(new FileWriter("output.txt")));
- }else{
- bf = new BufferedReader(new InputStreamReader(System.in));
- pw = new PrintWriter(new OutputStreamWriter(System.out));
- }
- // int q1 = Integer.parseInt(bf.readLine().trim());
- // for(te=1;te<=q1;te++) {
- n=Integer.parseInt(bf.readLine().trim());
- tasks=new ArrayList<>();
- for(int i=0;i<n;i++){
- String s[]=bf.readLine().trim().split("\\s+");
- int start, end, time;
- start=Integer.parseInt(s[0]);
- end=Integer.parseInt(s[1]);
- time=Integer.parseInt(s[2]);
- tasks.add(new Task(start, end, time));
- }
- solve(te);
- // }
- pw.print(str);
- pw.flush();
- // System.out.println(str);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment