IPCTRAIN getting TLE for 100 marks plz help (my Code is written in java)?

here below is my code which working for 40 marks but not for 100 marks… i know my program time complexity is near to 10^10 for worst case for 100 marks, but i dont know how to reduce time for my code, what to do further, after looking at editorial, i havn’t understood anything plz help me

   /*
     * To change this license header, choose License Headers in Project Properties.
     * To change this template file, choose Tools | Templates
     * and open the template in the editor.
 */
package codechef;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

/**
 *
 * @author Hemant Dhanuka
 */
public class IPCTRAIN1for100Marks {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        //        FastReader s = new FastReader();
        int totalCases = s.nextInt();
        for (int i = 0; i < totalCases; i++) {

            int NoOfTrainers = s.nextInt();
            int Days = s.nextInt();
            boolean DaysAvailablity[] = new boolean[Days];

            //       LinkedList<Node> l=new LinkedList<>();
            //           PriorityQueue pq=new PriorityQueue(new MyComparator());
            TreeSet pq = new TreeSet(new MyComparator());

            for (int j = 0; j < NoOfTrainers; j++) {
                int arrivalDay = s.nextInt();
                int totalLecutures = s.nextInt();
                int Sadness = s.nextInt();
                Node jiskoAddkarnaH = new Node(arrivalDay, totalLecutures, Sadness);
              
                pq.add(jiskoAddkarnaH);

            }
            //  System.out.println(pq);
            Iterator finalItr = pq.iterator();
            long MinimumSadness = 0;
            while (finalItr.hasNext()) {
                Node Trainee = (Node) finalItr.next();
                //System.out.println(Trainee.Sadness);
                for (int j = Trainee.arrivalDay; j <= Days && Trainee.totalLecutures > 0; j++) {
                    if (!DaysAvailablity[j - 1]) {
                        Trainee.totalLecutures--;
                        DaysAvailablity[j - 1] = true;

                    }
                }
                MinimumSadness += ((long) Trainee.totalLecutures) * Trainee.Sadness;

            }

            System.out.println(MinimumSadness);
        }
    }
}

class MyComparator implements Comparator<Object> {

    @Override
    public int compare(Object o1, Object o2) {
        if (((Node) o1).Sadness < ((Node) o2).Sadness) {
            return 1;
        } else if (((Node) o1).Sadness == ((Node) o2).Sadness) {
            if (((Node) o1).arrivalDay >= ((Node) o2).arrivalDay) {
                return 1;
            }

        }
        return -1;
    }

}

class Node {

    int arrivalDay;
    int totalLecutures;
    int Sadness;

    Node(int d, int t, int s) {
        this.arrivalDay = d;
        this.totalLecutures = t;
        this.Sadness = s;
    }
}

Priority queue should had worked for you. What difficulty you faced in this? Just today I and @kunal12 were discussing this problem, and kunal12 successfully solved it using priority queue in JAVA (I just told him logic).

Give a look to his code- https://www.codechef.com/viewsolution/14605809

1 Like

As far as i know priority queue is implemented using heap. so if you are using priority queue you are using heap.

2 Likes

@vijju123 bro… got AC answer

is there Any other approach to solve It… As stated in editorial,we can do it using heap… how! any idea?

I dont have much idea about heaps. Basically, the thing is, you need some data structure which sorts the data inputted in it according to something, and a custom data type to make life easier (its optional, but it makes it really comfortable while coding!).

Thats why i used priority queue. You can also solve it using sets etc. and other data structure, but it wont be this easy there and you will need to do many tweaks.

Yes, i heard that too. I am not much acquainted with theory stuff yet, left it for college to see.

yes u both are right
look at below link–explain it pretty well
http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

2 Likes

Thanks for link hemant :slight_smile:

:slight_smile: Thank u too bro, for helping me in this Problem as usual…