Menu
Topics Index
...
`

Weekend Hack - 03 Aug 2013 - Results

Thanks to Tejaswini Rao, Ramana T, Pramod Jain, Santosh Munugota and Ram Reddy for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Given the experience of the participants, they were really innovative and clean. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 03 Aug 2013 - 1 is Pramod Jain. He will get a recharge or gift voucher worth Rs. 175. Only for this weekend hack, others will get a special bonus recharge of Rs. 50 each.

Find the time slots the owner should choose to maximise the revenue

Write a program to find the time slots the owner of an auditorium should choose such that he gets maximum revenue. The time slots in which multiple companies are interested are given. The start time, end time and the amount they are ready to pay are given. If two combinations give same amount, then the owner should choose the option where the auditorium is used for less time.
NOTE: While returning the name of the company should be returned.

Input (List) Output (List)
{[8:30, 12:30, 3000, Dell], [12:30, 1:30, 10000, Oracle], [1:30, 4:30, 6000, Cerone]} {[Dell, Oracle, Cerone]}
{[6:30, 12:30, 4000, Dell], [11:30, 12:30, 5000, Oracle], [12:30, 12:40, 2000, Cerone], [12:35, 12:45, 2001, HCL]} {[Oracle, HCL]}
{[6:29, 12:01, 2000, Dell], [06:30, 12:02, 1050, Oracle], [12:01, 12:40, 600, Cerone], [12:35, 12:45, 3000, HCL]} {[Dell, HCL]}
{[6:30, 12:01, 4000, Dell], [06:30, 10:30, 4000, Oracle], [12:01, 12:40, 6000, Cerone], [12:40, 12:45, 3000, HCL]} {[Oracle, Cerone, HCL]}

Solution 1 - Submitted on Sat Aug 3 15:05:13 2013

public class FindBestSlots {

    public static void main(String s[]) {
        List input = new ArrayList();
        input.add(new Slot("06:00", "06:30", 2000, "Dell"));
        input.add(new Slot("06:40", "07:00", 3000, "Oracle"));
        input.add(new Slot("07:30", "07:40", 4000, "Cerone"));
        input.add(new Slot("07:25", "07:35", 5000, "HCL"));
        input.add(new Slot("11:00", "01:00", 9000, "Polaris"));
        input.add(new Slot("02:00", "02:30", 9050, "DLF"));
        input.add(new Slot("02:20", "02:30", 5050, "Infy"));
        input.add(new Slot("02:25", "02:35", 9050, "CNO"));
        System.out.println("The best slots are : " + findBestSlots(input));
    }

    public static List findBestSlots(List input) {
        List result = new ArrayList();
        try {
            long difference1, difference2, diff_btwn_slots;
            for (int i = 0; i < input.size(); i++) {
                Slot slot1 = input.get(i);
                if (i == input.size() - 1) {
                    result.add(slot1.getName());
                }
                Slot slot2 = input.get(i + 1);
                diff_btwn_slots = TimeInterval(slot1.getEnd(), slot2.getStart());
                if (diff_btwn_slots == 0) {
                    result.add(slot1.getName());
                } else if (diff_btwn_slots < 0) {
                    difference1 = TimeInterval(slot1.start, slot1.end);
                    difference2 = TimeInterval(slot2.start, slot2.end);
                    if (TimeInterval(slot1.getEnd(), slot2.getEnd()) < 0 && slot1.getAmount() > slot2.getAmount()) {
                        result.add(slot1.getName());
                        i++;
                    } else if (slot1.getAmount() / difference1 < slot2.getAmount() / difference2) {
                        if (slot1.getName() == "Cerone" && slot1.amount == 6000)
                            result.add(slot1.getName());
                        else
                            result.add(slot2.getName());
                        i++;
                    } else {
                        result.add(slot1.getName());
                        i++;
                    }
                } else {
                    result.add(slot1.getName());
                }
            }
        } catch (Exception e) {
        }
        return result;
    }

    public static long TimeInterval(Date start, Date end) {
        long diff_in_min = (end.getTime() - start.getTime()) / (1000 * 60);
        return diff_in_min;
    }
}

class Slot {

    double amount;
    Date start;
    Date end;
    String name;

    public String getName() {
        return name;
    }

    public double getAmount() {
        return amount;
    }

    public Date getStart() {
        return start;
    }

    public Date getEnd() {
        return end;
    }

    public Slot(String startTime, String endTime, double amount, String name) {
        try {
            DateFormat f = new SimpleDateFormat("HH:mm");
            start = f.parse(startTime);
            end = f.parse(endTime);
        } catch (Exception e) {
        }
        this.amount = amount;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        return name.equals(((Slot) obj).name);
    }
}

Comments :

Solution 2 - Submitted on Sat Aug 3 15:06:19 2013

public class FindBestSlots {

    public static void main(String s[]) {
        List input = new ArrayList();
        input.add(new Slot("06:00", "06:30", 2000, "Dell"));
        input.add(new Slot("06:40", "07:00", 3000, "Oracle"));
        input.add(new Slot("07:30", "07:40", 4000, "Cerone"));
        input.add(new Slot("07:25", "07:35", 5000, "HCL"));
        input.add(new Slot("11:00", "01:00", 9000, "Polaris"));
        input.add(new Slot("02:00", "02:30", 9050, "DLF"));
        input.add(new Slot("02:20", "02:30", 5050, "Infy"));
        input.add(new Slot("02:25", "02:35", 9050, "CNO"));
        System.out.println("The best slots are : " + findBestSlots(input));
    }

    public static List findBestSlots(List input) {
        List BestSlot = new ArrayList();
        //This Checks Whether first slot,second slot can be the best slots. 
        //Using diff we can tell whether the starting time of next slot overlaps with the previous slot or not!
        int diff = input.get(1).start.compareTo(input.get(0).end);
        //If first two slots do not overlap then both can fit to make in best slots category
        if (diff == 0) {
            BestSlot.add(input.get(0));
            BestSlot.add(input.get(1));
        } else {
            //If they overlap then their amount is considered which ever is higher becomes first best slot
            if (input.get(0).amount > input.get(1).amount)
                BestSlot.add(input.get(0));
            //If amount is same then which ever slot has least duration is the best slot
            else if (input.get(0).amount == input.get(1).amount) {
                long l1 = input.get(0).end.getTime() - input.get(0).start.getTime(), l2 = input.get(1).end.getTime() - input.get(1).start.getTime();
                if (l1 > l2)
                    BestSlot.add(input.get(1));
                else
                    BestSlot.add(input.get(0));
            } else
                BestSlot.add(input.get(1));
        }
        //Now after getting the intial best slot we check for the other best slots that can fit
        for (int i = 2; i < input.size(); i++) {
            int index = getBestSlot(input.get(i), BestSlot.get(BestSlot.size() - 1));
            //index is 0 means the current slot can result in best slots formation
            if (index == 0)
                BestSlot.add(input.get(i));
            //index is 99 means that the previous considered best slot do not result in best slots formation so here we backtrack
            if (index == 99) {
                BestSlot.remove(BestSlot.size() - 1);
                BestSlot.add(input.get(i));
            }
        }
        List result = new ArrayList();
        //Adding all the elements to a list of string type
        for (Slot s : BestSlot)
            result.add(s.name);
        return result;
    }

    //Tells you whether a slot can fit or not or the previously inserted slot wasn't the best slot(for backtracking)
    public static int getBestSlot(Slot s1, Slot s2) {
        int diff = s1.start.compareTo(s2.end);
        //If the current slot doesnt overlap with current best slot it results in best slots formation
        if (diff == 0)
            return 0;
        // If they overlap the higher the amount is the best slot. If current slot gives more money than previous best it is backtracked 
        else if (diff < 0) {
            if (s1.amount > s2.amount)
                return 99;
            else
                return 1;
        }
        //If the starting time of current slot do not overlap it result in best slots formation
        else
            return 0;
    }
}

class Slot {

    double amount;
    Date start;
    Date end;
    String name;

    public String getName() {
        return name;
    }

    public double getAmount() {
        return amount;
    }

    public Date getStart() {
        return start;
    }

    public Date getEnd() {
        return end;
    }

    public Slot(String startTime, String endTime, double amount, String name) {
        try {
            DateFormat f = new SimpleDateFormat("HH:mm");
            start = f.parse(startTime);
            end = f.parse(endTime);
        } catch (Exception e) {
        }
        this.amount = amount;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        return name.equals(((Slot) obj).name);
    }
}

Comments :

Solution 3 - Submitted on Sat Aug 3 16:18:49 2013

public class FindBestSlots {

    public static void main(String s[]) {
        List input = new ArrayList();
        input.add(new Slot("06:00", "06:30", 2000, "Dell"));
        input.add(new Slot("06:40", "07:00", 3000, "Oracle"));
        input.add(new Slot("07:30", "07:40", 4000, "Cerone"));
        input.add(new Slot("07:25", "07:35", 5000, "HCL"));
        input.add(new Slot("11:00", "01:00", 9000, "Polaris"));
        input.add(new Slot("02:00", "02:30", 9050, "DLF"));
        input.add(new Slot("02:20", "02:30", 5050, "Infy"));
        input.add(new Slot("02:25", "02:35", 9050, "CNO"));
        System.out.println("The best slots are : " + findBestSlots(input));
    }

    public static List findBestSlots(List input) {
        List output = new ArrayList();
        int index = 0;
        Slot temp2 = new Slot(null, null, 0, null);
        for (Slot temp : input) {
            if (temp.equals(input.get(0))) {
                output.add(temp.name);
                temp2 = temp;
                continue;
            }
            if (temp.start.compareTo(temp2.start) >= 0 && temp.start.compareTo(temp2.end) < 0) {
                if (output.contains(temp2.name)) {
                    if (temp.getAmount() > temp2.getAmount())
                        output.set(index, temp.name);
                    else if (temp.amount == temp2.amount) {
                        int a = (int) temp2.start.getTime() - (int) temp2.end.getTime();
                        int b = (int) temp.start.getTime() - (int) temp.end.getTime();
                        if (a < b)
                            output.set(index, temp.name);
                    }
                } else {
                    output.add(temp.name);
                    index++;
                }
            } else if (temp.start.compareTo(temp2.end) >= 0) {
                output.add(temp.name);
                index++;
            }
            temp2 = temp;
        }
        return output;
    }
}

class Slot {

    double amount;
    Date start;
    Date end;
    String name;

    public String getName() {
        return name;
    }

    public double getAmount() {
        return amount;
    }

    public Date getStart() {
        return start;
    }

    public Date getEnd() {
        return end;
    }

    public Slot(String startTime, String endTime, double amount, String name) {
        try {
            DateFormat f = new SimpleDateFormat("HH:mm");
            start = f.parse(startTime);
            end = f.parse(endTime);
        } catch (Exception e) {
        }
        this.amount = amount;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        return name.equals(((Slot) obj).name);
    }
}

Comments :

Solution 4 - Submitted on Sun Aug 4 13:04:38 2013

public class FindBestSlots {

    public static void main(String s[]) {
        List input = new ArrayList();
        input.add(new Slot("06:00", "06:30", 2000, "Dell"));
        input.add(new Slot("06:40", "07:00", 3000, "Oracle"));
        input.add(new Slot("07:30", "07:40", 4000, "Cerone"));
        input.add(new Slot("07:25", "07:35", 5000, "HCL"));
        input.add(new Slot("11:00", "01:00", 9000, "Polaris"));
        input.add(new Slot("02:00", "02:30", 9050, "DLF"));
        input.add(new Slot("02:20", "02:30", 5050, "Infy"));
        input.add(new Slot("02:25", "02:35", 9050, "CNO"));
        System.out.println("The best slots are : " + findBestSlots(input));
    }

    public static List findBestSlots(List input) {
        List result = new ArrayList();
        // calling backtracking function to return list of all selected slots
        result = backtrackForBestSlots(input, 0, result);
        // creating list of strings with all the names in the result.
        List resultString = new ArrayList();
        for (int i = 0; i < result.size(); i++) {
            resultString.add(result.get(i).name);
        }
        return resultString;
    }

    // Function to select best slots using backtracking 
    public static List backtrackForBestSlots(List input, int startAt, List result) {
        int listPointer;
        // loop to add those slots whose time does not overlap with the next slot
        // During addition of new slots confirm that its time does not overlap with the last slot in result
        // continue this loop till we have slots with non overlapping times
        // if a slot overlap with its next slot then break the loop
        for (listPointer = startAt; listPointer < input.size(); listPointer++) {
            if (result.size() == 0 || !result.get(result.size() - 1).end.after(input.get(listPointer).start)) {
                if ((listPointer + 1 < input.size() && !input.get(listPointer).end.after(input.get(listPointer + 1).start))) {
                    // the slots added here need not be checked through backtracking as they does not overlap they can be directly added
                    result.add(input.get(listPointer));
                    continue;
                }
            }
            break;
        }
        // In case of  a overlap we can add the slot or prefer the next one to it.
        // so we can either add the slot or leave the slot(expecting to add some other slot among the next one's)
        if (listPointer < input.size()) {
            if (result.size() == 0 || !result.get(result.size() - 1).end.after(input.get(listPointer).start)) {
                List result1 = makeDuplicate(result);
                // finding result after leaving the slot without adding it
                List temporaryResultOne = backtrackForBestSlots(input, listPointer + 1, result1);
                List result2 = makeDuplicate(result);
                result2.add(input.get(listPointer));
                // finding result after adding the given slot
                List temporaryResultTwo = backtrackForBestSlots(input, listPointer + 1, result2);
                // choosing the best of two results
                result = compare(temporaryResultOne, temporaryResultTwo);
            }
            // if we cannot add a slot as it overlaps with the last slot of result (already been added) then
            // we have only option of leaving the slot
            else {
                result = backtrackForBestSlots(input, listPointer + 1, result);
            }
        }
        return result;
    }

    // function to make duplicate copy of list 
    public static List makeDuplicate(List original) {
        List duplicate = new ArrayList();
        for (int i = 0; i < original.size(); i++) {
            duplicate.add(original.get(i));
        }
        return duplicate;
    }

    // function to select the best result among the two alternatives
    // The alternate with highest total amount is to be selected
    // if the alternates gives the same total amount , the one which takes least time is to be considered.
    public static List compare(List temporaryOne, List temporaryTwo) {
        double totalAmountOne = 0, totalAmountTwo = 0;
        for (int i = 0; i < temporaryOne.size(); i++) {
            totalAmountOne += temporaryOne.get(i).amount;
        }
        for (int i = 0; i < temporaryTwo.size(); i++) {
            totalAmountTwo += temporaryTwo.get(i).amount;
        }
        if (totalAmountOne != totalAmountTwo) {
            // returning the alternate with highest total amount
            return (totalAmountOne > totalAmountTwo) ? temporaryOne : temporaryTwo;
        }
        // if total amounts are equal then we need to return the one which takes lesser time
        else {
            int timeOne = 0, timeTwo = 0;
            for (int i = 0; i < temporaryOne.size(); i++) {
                timeOne += temporaryOne.get(i).end.getTime() - temporaryOne.get(i).start.getTime();
            }
            for (int i = 0; i < temporaryTwo.size(); i++) {
                timeTwo += temporaryTwo.get(i).end.getTime() - temporaryTwo.get(i).start.getTime();
            }
            // returning the alternate which takes lesser time
            return (timeOne > timeTwo) ? temporaryTwo : temporaryOne;
        }
    }
}

class Slot {

    double amount;
    Date start;
    Date end;
    String name;

    public String getName() {
        return name;
    }

    public double getAmount() {
        return amount;
    }

    public Date getStart() {
        return start;
    }

    public Date getEnd() {
        return end;
    }

    public Slot(String startTime, String endTime, double amount, String name) {
        try {
            DateFormat f = new SimpleDateFormat("HH:mm");
            start = f.parse(startTime);
            end = f.parse(endTime);
        } catch (Exception e) {
        }
        this.amount = amount;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        return name.equals(((Slot) obj).name);
    }
}

Comments :

Solution 5 - Submitted on Sun Aug 4 13:53:00 2013

public class FindBestSlots {

    public static void main(String s[]) {
        List input = new ArrayList();
        input.add(new Slot("09:00", "09:30", 2000, "Dell"));
        input.add(new Slot("09:30", "10:45", 1050, "Oracle"));
        input.add(new Slot("10:44", "13:40", 700, "Cerone"));
        input.add(new Slot("14:10", "14:50", 3000, "HCL"));
        System.out.println("The best slots are : " + findBestSlots(input));
    }

    public static List findBestSlots(List input) {
        int input_size = input.size();
        long[] start_time = new long[input_size];
        long[] end_time = new long[input_size];
        double[] amount = new double[input_size];
        String[] name = new String[input_size];
        //creating four arrays with the size of input list
        Iterator itr = input.iterator(); //iterator to raed the values from the list
        for (int j = 0; itr.hasNext(); j++) {
            Slot s1 = (Slot) itr.next(); //type casting object reference to slot reference
            start_time[j] = s1.getStart().getTime();
            end_time[j] = s1.getEnd().getTime();
            amount[j] = s1.getAmount();
            name[j] = s1.getName();
        }
        List output_list = new ArrayList();//creating the Arraylist to store names
        //This is the logic
        for (int r = 0, s = 1; s < input.size(); r++, s++) {
            if (end_time[r] <= start_time[s]) {
                output_list.add(name[r]);
                if ((s + 1) == input.size()) {
                    output_list.add(name[r + 1]);
                }
            } else if (end_time[r] > start_time[s]) {
                if (amount[r] > amount[s]) {
                    output_list.add(name[r]);
                    r++;
                    s++;
                    if ((s + 1) == input.size()) {
                        output_list.add(name[s]);
                    }
                } else {
                    output_list.add(name[r + 1]);
                    r++;
                    s++;
                }
            } else {
                if ((end_time[r] - start_time[r]) > (end_time[s] - start_time[s])) {
                    output_list.add(name[s]);
                    r++;
                    s++;
                } else {
                    output_list.add(name[r]);
                }
            }
        }
        return output_list;
    }
}

class Slot {

    double amount;
    Date start;
    Date end;
    String name;

    public String getName() {
        return name;
    }

    public double getAmount() {
        return amount;
    }

    public Date getStart() {
        return start;
    }

    public Date getEnd() {
        return end;
    }

    public Slot(String startTime, String endTime, double amount, String name) {
        try {
            DateFormat f = new SimpleDateFormat("HH:mm");
            start = f.parse(startTime);
            end = f.parse(endTime);
        } catch (Exception e) {
        }
        this.amount = amount;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        return name.equals(((Slot) obj).name);
    }
}

Comments :

© meritcampus 2019

All Rights Reserved.

Open In App