CODEWITHSUNDEEP
javaalgorithmdata-structurescollections
user9732090
user9732090

Reputation:

Java - Conflict Resolution for DVR

I am trying to develop a program that takes as input the taping schedule of a DVR and determines which shows are recorded and at what time. Multiple shows can be on at the same times which are set for recording and DVR can only record a single show at once. There can be multiple airings of the same show. If all airings of a particular show conflict with another show(s), then the show(s) with the highest priority will be recorded. In other words, you may have to consider the priority of more than two shows when resolving conflicts. A show should be recorded only once.

Input:-

The input data contains a list of shows to record and the day and times they will be aired. The shows are listed in priority order, with the first show having the highest priority. Each line contains the name of the show followed by a series of days and times. Each day and time consists of a three-letter abbreviation for a day of the week (i.e., one of SUN, MON, TUE, WED, THU, FRI, or SAT), followed by the time of day, expressed in “military time''. All shows start on the hour and will last less than one hour. The airings for each show are listed in no particular order. There is no limit to the number of airings a show may have. The delimiter for the input data is the '/' character.

Example:-

OUTPUT

List displaying the show name (same order) and the time it will be recorded that week. If the show cannot be scheduled, you should output the string “Impossible”.

What data structure shall I use for this? A similar Question with answer already there but I am not sure how I can use it, since there can be multiple airing of the same show and priority order of programmes is defined.

Code to fetch input from file.(File content is same as example text) and convert it into Two dimensional array.

Format:- {{Programme1,WED,2000,SUN,2200},{Programme2,WED,2000},so on...}

    public static void main(String[] args) {
    // TODO Auto-generated method stub
    String[][] input = readInput();
    input = schedules(input);
    for (int i = 0; i < input.length; ++i) {
        System.out.println(input[i][0]+" "+input[i][1]);
    }
}
public static String[][] readInput() {
    List<String> lines = null;
    String path = "input.txt";
    try {
        lines = Files.readAllLines(Paths.get(path), StandardCharsets.UTF_8);
    } catch (IOException ioEx) {
        System.out.println(ioEx.getMessage());
    }
    int i = 0;
    String[][] inputArray = new String[lines.size()][];
    for (String temp: lines)    {
        StringTokenizer st1 = new StringTokenizer(temp, "/");
        int j = st1.countTokens();
        inputArray[i] = new String[j];
        st1 = new StringTokenizer(temp, "/");
        for(int k=0; k < j;++k) {
            inputArray[i][k] = st1.nextToken();
        }
        ++i;
    }
    return inputArray;
}

Posting complete solution:-

    public static String[][] schedules(String[][] airingSchedule) {
    String prevValue;
    Map<String,String> aLinkedHashmap = new LinkedHashMap<>();
    for(int i = 0;i < airingSchedule.length;++i)    {
        for(int j =airingSchedule[i].length - 1; j > 1;j-=2)    {
            if(aLinkedHashmap.containsKey(airingSchedule[i][j-1]+airingSchedule[i][j])) {
                prevValue = aLinkedHashmap.put(airingSchedule[i][j-1]+airingSchedule[i][j], airingSchedule[i][0]);
                if(!aLinkedHashmap.containsValue(prevValue))    {
                    aLinkedHashmap.put(airingSchedule[i][j-1]+airingSchedule[i][j], prevValue);
                }
            } else  {
                aLinkedHashmap.put(airingSchedule[i][j-1]+airingSchedule[i][j], airingSchedule[i][0]);
            }
        }
    }
    Iterator<String> it = aLinkedHashmap.keySet().iterator();
    Map<String,String> map = new LinkedHashMap<>();
    // Removing multiple occurrence of shows
    while(it.hasNext()) {
        String key = it.next(); 
        String val = aLinkedHashmap.get(key);
        if(!map.containsKey(val))
            map.put(val, key);
    }
    String[][] output = new String[airingSchedule.length][2];
    for(int i =0; i < airingSchedule.length ;++i)   {
        if(map.containsKey(airingSchedule[i][0]))   {
            output[i][1] = map.get(airingSchedule[i][0]);
            output[i][1] = output[i][1].substring(0,3)+" "+output[i][1].substring(3);
            output[i][0] = airingSchedule[i][0];
        } else  {
            output[i][1] = "Impossible";
            output[i][0] = airingSchedule[i][0];
        }
    }
    return output;
}

Upvotes: 0

Views: 161

Answers (1)

Developer
Developer

Reputation: 544

You can use LinkedHashMap DS(to preserve the order) wherein you can have DAY+Time as a key and programme name as value. Then:-

  1. Check if the key exists before inserting it to DS.
  2. If Key exists, then put the new value and store the previous value associated with key.
  3. Check if previous value(of Step 2) still exists in DS.
  4. If value(of Step 2) does not exist, Restore the previous value with this key.
  5. If Key(of Step 1) does not exist, add item to DS. Here we might have multiple entries for the same value (programme).
  6. Remove multiple entries of same value(programme).
  7. Write output in desired format.

Upvotes: 0

Related Questions