Sunscreen

Given a series of cows with min an max sun shine acceptation and some bottles of lotion, each lotion has an effective SPF value and count of cows that can use it. A bottle of lotion is required to be in acceptation range of a cow if it is applied to that cow. The question is asking the maximum number of cows that can use lotion.

The solution combines greedy strategy as well as application of PriorityQueue. At first we sort the cows according to there min value and lotion according to their SPF value. Then from the first lotion, we first find all cows that min value is below the SPF value, We add them to the PriorityQueue so that each time we can get a cow with lowest max value out. It is obviously if we pick out cows in this order, if a cow's max is lower than current SPF, it and all cows before won't be able to apply this lotion. We also have, if a bottle of lotion can be applied to cow a and for a bottle of lotion that has higher SPF but lower than a.max value, a can also apply the latter bottle of lotion. But reversely this condition won't holds. That's why the greedy strategy will work. Every time we apply lotion to cows in the range but with lowest max value, that won't affect the total count.

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

class Cow implements Comparable<Cow> {

    int max;
    int min;

    public Cow(int min, int max) { 
        this.min = min;
        this.max = max;
    }

    public int compareTo(Cow b) {
        return this.min - b.min;
    }
}

class Lotion implements Comparable<Lotion> {

    int spf;
    int count;

    public Lotion(int spf, int count) { 
        this.spf = spf;
        this.count = count;
    }

    public int compareTo(Lotion b) {
        return this.spf - b.spf;
    }
}

public class Sunscreen {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int C = in.nextInt(), L = in.nextInt();

            Cow[] cows = new Cow[C];
            Lotion[] lotions = new Lotion[L];

            for (int i = 0; i < C; i++) {
                cows[i] = new Cow(in.nextInt(), in.nextInt());
            }

            for (int i = 0; i < L; i++) {
                lotions[i] = new Lotion(in.nextInt(), in.nextInt());
            }

            Arrays.sort(cows);
            Arrays.sort(lotions);

            int c = 0;
            int l = 0;
            int count = 0;

            PriorityQueue<Cow> pq = new PriorityQueue<Cow>(C, new Comparator<Cow>() {
                public int compare(Cow a, Cow b) {
                    return a.max - b.max;
                }
            });

            while (l < L) {
                Lotion lo = lotions[l++];

                while (c < C && cows[c].min <= lo.spf) {
                    pq.offer(cows[c++]);
                }

                while (lo.count > 0 && !pq.isEmpty()) {
                    Cow cow = pq.poll();
                    if (cow.max >= lo.spf) {
                        count++;
                        lo.count--;
                    }
                }
            }

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