കോഴ്സ് ഷെഡ്യൂൾ II - ലീറ്റ് കോഡ്


വൈഷമ്യ നില മീഡിയം
വീതിയുടെ ആദ്യ തിരയൽ ആഴത്തിലുള്ള ആദ്യ തിരയൽ ഗ്രാഫ് ടോപ്പോളജിക്കൽ അടുക്കുക

ചില കോഴ്സുകൾക്ക് മുൻ‌വ്യവസ്ഥകൾ ഉള്ള n എണ്ണം കോഴ്‌സുകളിൽ (0 മുതൽ n-1 വരെ) നിങ്ങൾ പങ്കെടുക്കണം. ഉദാഹരണത്തിന്: ജോഡി [2, 1] കോഴ്‌സ് 2 ൽ പങ്കെടുക്കാൻ പ്രതിനിധീകരിക്കുന്നു നിങ്ങൾ കോഴ്‌സ് 1 എടുത്തിരിക്കണം. മൊത്തം കോഴ്‌സുകളുടെ എണ്ണത്തെയും അവയുടെ മുൻവ്യവസ്ഥകളുള്ള കോഴ്‌സുകളുടെ ലിസ്റ്റിനെയും പ്രതിനിധീകരിക്കുന്ന ഒരു സംഖ്യ n നൽകി. നിങ്ങൾക്ക് എല്ലാ n കോഴ്സുകളും പൂർത്തിയാക്കാൻ കഴിയുന്ന ഏത് ഓർഡറും ഞങ്ങൾ നൽകേണ്ടതുണ്ട്. സാധ്യമായ ഉത്തരം ഇല്ലെങ്കിൽ ശൂന്യമായി മടങ്ങുക ശ്രേണി. ഒന്നിലധികം ഉത്തരങ്ങളുണ്ടെങ്കിൽ നിങ്ങൾക്ക് ആവശ്യമുള്ളത് നൽകുക.

കോഴ്സ് ഷെഡ്യൂൾ II - ലീറ്റ് കോഡ്

ഉദാഹരണം

ഇൻപുട്ട്:  4

[[1,0], [2,0], [3,1], [3,2]]

ഔട്ട്പുട്ട്: [0, 1, 2, 3,]

ഇൻപുട്ട്: 2

[[1, 0]]

ഔട്ട്പുട്ട്: [0, 1,]

ആദ്യ തിരയൽ ഉപയോഗിക്കുന്നു

കോഴ്‌സ് ഷെഡ്യൂൾ II നായുള്ള അൽഗോരിതം - ലീറ്റ്കോഡ്

  1. കോഴ്സുകളുടെ എണ്ണത്തെയും അവയുടെ മുൻവ്യവസ്ഥകളെയും സംഭരിക്കുന്നതിനുള്ള 2 ഡി അറേ കോഴ്സും കോഴ്‌സുകളുടെ എണ്ണത്തെ പ്രതിനിധീകരിക്കുന്ന ഒരു സംഖ്യ n സമാരംഭിക്കുക.
  2. കോഴ്‌സ് അറേ ശൂന്യമായ പ്രിന്റ് ശൂന്യമായ അറേ ആണെങ്കിൽ.
  3. മുൻ‌വ്യവസ്ഥകൾ‌ ആവശ്യമുള്ള കോഴ്‌സുകൾ‌ സംഭരിക്കുന്നതിന് വലുപ്പം n ന്റെ ഒരു അറേ pCounter സൃഷ്‌ടിക്കുക.
  4. 0 ൽ നിന്ന് n-1 ലേക്ക് നീക്കുക, pCounter വർദ്ധിപ്പിക്കുക [കോഴ്സ് [i] [0]].
  5. ഒരു വെക്റ്റർ സൃഷ്ടിക്കുക വരി എല്ലാ മുൻവ്യവസ്ഥകളും സംഭരിക്കുന്നതിന്.
  6. 0 ൽ നിന്ന് n-1 ലേക്ക് നീക്കി നിലവിലെ സൂചികയുടെ pCounter ലെ മൂല്യം 0 ആണോയെന്ന് പരിശോധിക്കുക, ക്യൂവിൽ നിലവിലെ സൂചിക ചേർക്കുക.
  7. N വലുപ്പത്തിന്റെ ഒരു അറേ ഫലം സമാരംഭിക്കുക.
  8. ക്യൂ ശൂന്യമല്ലെങ്കിലും ക്യൂവിലെ അവസാന ഘടകം നീക്കംചെയ്‌ത് ഫല അറേയിലും ഒരു സംഖ്യയിലും സംഭരിക്കുക.
  9. ഒരു ആന്തരിക ലൂപ്പ് സൃഷ്‌ടിച്ച് കോഴ്‌സ് അറേയിലെ [] [1] ലെ മൂല്യം c കുറയൽ pCounter [കോഴ്‌സ് [i] [0]] ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക.
  10. PCounter [കോഴ്സ് [i] [0]] 0 ക്യൂസ് കോഴ്സ് [i] [0] ആണോയെന്ന് പരിശോധിക്കുക.
  11. ഫല ശ്രേണി അച്ചടിക്കുക.

നടപ്പിലാക്കൽ

കോഴ്സ് ഷെഡ്യൂൾ II നായുള്ള സി ++ പ്രോഗ്രാം - ലീറ്റ് കോഡ്

#include <bits/stdc++.h> 
using namespace std; 
  
int len = 4;

void findOrder(int n, int course[4][2]){
    if(course == NULL){
        cout<<"empty array";
    }
    
    int pCounter[n];
    for(int i=0; i<len; i++){
        pCounter[course[i][0]]++;
    }
    
    vector<int> queue;
    for(int i=0; i<n; i++){
        if(pCounter[i]==0){
            queue.push_back(i);
        }
    }
    
    int numNoPre = queue.size();
    
    int result[n];
    int j=0;
    
    while(queue.size()!=0){
        int c = 0;
        if(!queue.empty()){
            c = queue.back();
            queue.pop_back();
        }    
        result[j++]=c;
        
        for(int i=0; i<len; i++){
            if(course[i][1]==c){
                pCounter[course[i][0]]--;
                if(pCounter[course[i][0]]==0){
                    queue.push_back(course[i][0]);
                    numNoPre++;
                }
            }
        
        }
    }
    
    cout<<"[";
    for(int i=0; i<n; i++){
        cout<<result[i]<<",";
    }
    cout<<"]";
}
  
int main(){
    
    int n = 4;
        int course[4][2] = {{1,0}, {2,0}, {3,1}, {3,2}};
        
        findOrder(n, course);
    
    return 0; 
}
[0,2,1,3,]

കോഴ്‌സ് ഷെഡ്യൂൾ II നായുള്ള ജാവ പ്രോഗ്രാം - ലീറ്റ് കോഡ്

import java.util.*;
    
class selection{
    static int[] findOrder(int n, int[][] course) {
        if(course == null){
            throw new IllegalArgumentException("empty array");
        }
        
        int len = course.length;
        
        if(len == 0){
            int[] res = new int[n];
            for(int m=0; m<n; m++){
                res[m]=m;
            }
            return res;
        }
    
        int[] pCounter = new int[n];
        for(int i=0; i<len; i++){
            pCounter[course[i][0]]++;
        }
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i=0; i<n; i++){
            if(pCounter[i]==0){
                queue.add(i);
            }
        }
        
        int numNoPre = queue.size();
        
        int[] result = new int[n];
        int j=0;
        
        while(!queue.isEmpty()){
            int c = queue.remove();
            result[j++]=c;
            
            for(int i=0; i<len; i++){
                if(course[i][1]==c){
                    pCounter[course[i][0]]--;
                    if(pCounter[course[i][0]]==0){
                        queue.add(course[i][0]);
                        numNoPre++;
                    }
                }
            
            }
        }
        
        if(numNoPre==n){
            return result;
        }
        else{
            return new int[0];
        }
    }
    
    public static void main (String[] args) {
        int n = 4;
        int[][] course = {{1,0}, {2,0}, {3,1}, {3,2}};
        
        int[] result = findOrder(n, course);
        
        System.out.print("[");
        for(int i=0; i<result.length; i++){
            System.out.print(result[i]+",");
        }
        System.out.print("]");
    }
}
[0,1,2,3,]

കോഴ്‌സ് ഷെഡ്യൂൾ II- നുള്ള സങ്കീർണ്ണത വിശകലനം - ലീട്ട് കോഡ്

സമയ സങ്കീർണ്ണത

O (Q * M) Q ന്റെ വലുപ്പം ഇവിടെ വെക്ടർ അല്ലെങ്കിൽ മുൻവ്യവസ്ഥകൾ അടങ്ങിയ പട്ടിക, M എന്നത് വരികളുടെ എണ്ണം അതായത് നൽകിയ ജോഡികളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (M * N) ഇവിടെ M വരികളുടെ എണ്ണത്തെയും N നൽകിയ കോഴ്‌സ് അറേയിലെ നിരകളുടെ എണ്ണത്തെയും സൂചിപ്പിക്കുന്നു.

അവലംബം