LIKE CODING: MJ [41] Schedule Courses

LIKE CODING: MJ [41] Schedule Courses
schedules gives a number of courses and its possible time slots. Determine if there is a schedule in which all the courses can be arranged without conflicts.

bool valid(vector<pair<int, int>> &sch, pair<int, int> intv){

    for(auto s:sch){

        if(intv.second>s.first && intv.first<s.second) return false;

    }

    return true;

}

 

bool bt(unordered_map<int, vector<pair<int, int>>> &schedules, vector<pair<int, int>> &sch, int p, int n){

    if(p==n){

        return true;

    }else{

        sort(sch.begin(), sch.end());

        for(auto s:schedules[p]){

            if(valid(sch, s)){

                sch.push_back(s);

                if(bt(schedules, sch, p+1, n)) return true;

                sch.pop_back();

            }

        }

        return false;

    }

}

 

bool validSchedule(unordered_map<int, vector<pair<int, int>>> &schedules){

    vector<pair<int, int>> sch;

    bool ret =  bt(schedules, sch, 0, schedules.size());

    cout<<"one schedule:"<<endl;

    for(auto s:sch){

        cout<<" ("<<s.first<<" "<<s.second<<") ";

    }

    cout<<endl;

    return ret;

}

 

int main(){

  unordered_map<int, vector<pair<int, int>>> schedules;

  schedules[0] = {pair<int, int>(1,3), pair<int, int>(2,4)};

  schedules[1] = {pair<int, int>(3,5), pair<int, int>(7,9)};

  schedules[2] = {pair<int, int>(2,3)};

  cout<<validSchedule(schedules)<<endl;

  return 0;

}

Read full article from LIKE CODING: MJ [41] Schedule Courses