(SPOJ) Telemarketing - Solution 2

Link to the problem: http://br.spoj.com/problems/TELEMAR7/

If you want to see another solution for this problem, click here.

The solution below uses a PriorityQueue to keep the sellers and their calls. It provides the seller who has the shortest call. If more than a call has the same minimum value, it provides the seller whose id is the minimum.


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

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        String[] s = line.split("\\s");
        int numSellers = Integer.parseInt(s[0]);
        int numCalls = Integer.parseInt(s[1]);
       
        Queue<Seller> queue = new PriorityQueue<Seller>(); // keep the time of the calls for each seller
        for (int i = 0; i < numSellers; i++) {
            queue.add(new Seller(i, 0));
        }
       
        int[] sellersCalls = new int[numSellers]; // keep how many calls each seller did
        for (int i = 0; i < numCalls; i++) {
            Seller sl = queue.poll();
            int currCall = sl.call + Integer.parseInt(br.readLine());
            sellersCalls[sl.id]++;
            queue.add(new Seller(sl.id, currCall));
        }
       
        for (int i = 0; i < numSellers; i++) {
            System.out.println((i+1) + " " + sellersCalls[i]);
        }
                          
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Seller implements Comparable<Seller> {
    int id;
    int call;
   
    public Seller(int id, int call) {
        this.id = id;
        this.call = call;
    }
   
    public int compareTo(Seller s) {
        if (this.call-s.call == 0) {
            return this.id-s.id;
        }
        return this.call-s.call;
    }
}