首页 > 其他分享 >1494. Parallel Courses II (Hard)

1494. Parallel Courses II (Hard)

时间:2023-06-19 11:13:31浏览次数:51  
标签:course int study Hard II Courses semester take courses

Description

1494. Parallel Courses II (Hard)

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei. Also, you are given the integer k.

In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking.

Return the minimum number of semesters needed to take all courses. The testcases will be generated such that it is possible to take every course.

 

Example 1:

Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
Output: 3
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 2 and 3.
In the second semester, you can take course 1.
In the third semester, you can take course 4.

Example 2:

Input: n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4
Explanation: The figure above represents the given graph.
In the first semester, you can only take courses 2 and 3 since you cannot take more than two per
semester.
In the second semester, you can take course 4.
In the third semester, you can take course 1.
In the fourth semester, you can take course 5.

 

Constraints:

  • 1 <= n <= 15
  • 1 <= k <= n
  • 0 <= relations.length <= n * (n-1) / 2
  • relations[i].length == 2
  • 1 <= prevCoursei, nextCoursei <= n
  • prevCoursei != nextCoursei
  • All the pairs [prevCoursei, nextCoursei] are unique.
  • The given graph is a directed acyclic graph.

Solution

This problem readily brings to mind the concept of topological sorting, followed by a greedy approach. However, this approach is erroneous! In essence, this problem is NP-Hard and can only be solved through brute force.

Let's consider the application of state-compressed dynamic programming (DP). The subproblems are relatively straightforward to identify. We start by choosing $1, 2$, followed by selecting $3, 4, 5 $(meeting the prerequisites). We can use a binary number, $to$$study$, to represent the set of courses we currently need to study, and $pre[j]$ to represent the set of prerequisite courses for course $j$. The recursive function can be denoted as $dfs(to$$study, pre)$.

Within this recursive function, we first calculate the set of courses $tmp$ that can be studied at the moment:

for (int i = 0; i < n; ++i) {
    if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
        // Indicates that i is in to_study and its prerequisite courses have been studied (or it has no prerequisites)
        tmp = (tmp | (1 << i));
        ++cnt;
    }
}

If the number of courses $cnt$ in $tmp$ is less than or equal to k, we can directly study all the courses in the $tmp$ set. Otherwise, we iterate through the subsets of $tmp$. If the number of courses $m$ in subset $i$ satisfies $m <= k$, we study that subset. In the next recursive call, the courses to be studied can be represented as $to$_$study \oplus i$.

For a method to enumerate subsets, refer to Bitwise Operations and Sets.

In C++, the library function to count the number of $1$ bits in a binary number is __builtin_popcount(i).

Code

class Solution {
  public:
    static auto dfs(int to_study, vector<int> &cache, int full, vector<int> &pre, int n, int k) -> int {
        if (to_study == 0) {
            return 0;
        }
        if (cache[to_study] != -1) {
            return cache[to_study];
        }
        int studied = (to_study ^ full);
        int count = 0; // Count the number of courses that can be studied
        int tmp = 0;   // Courses to be studied in this recursive call
        for (int i = 0; i < n; ++i) {
            if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
                // Indicates that i is in to_study and its prerequisite courses have been studied (or it has no prerequisites)
                tmp = (tmp | (1 << i));
                ++count;
            }
        }
        if (count <= k) {
            cache[to_study] = dfs(to_study ^ tmp, cache, full, pre, n, k) + 1;
            return cache[to_study];
        }
        int result = INT_MAX;
        for (int i = tmp; i != 0; i = (i - 1) & tmp) {
            if (__builtin_popcount(i) <= k) {
                result = min(result, dfs(to_study ^ i, cache, full, pre, n, k) + 1);
            }
        }
        cache[to_study] = result;
        return cache[to_study];
    }

    int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) {
        vector<int> pre(n);
        for (auto &vec : relations) {
            int x = vec[0] - 1, y = vec[1] - 1; // Adjusting indices to start from 0 to n-1
            pre[y] = (pre[y] | (1 << x));
        }
        int full = (1 << n) - 1; // Full set
        vector<int> cache(1 << n, -1);
        return dfs(full, cache, full, pre, n, k);
    }
};

标签:course,int,study,Hard,II,Courses,semester,take,courses
From: https://www.cnblogs.com/zwyyy456/p/17490598.html

相关文章

  • C++面试八股文:什么是RAII?
    C++面试八股文:什么是RAII?某日二师兄参加XXX科技公司的C++工程师开发岗位第13面:面试官:什么是RAII?二师兄:RAII是ResourceAcquisitionIsInitialization的缩写。翻译成中文是资源获取即初始化。面试官:RAII有什么特点和优势?二师兄:主要的特点是,在对象初始化时获取资源,在对......
  • 552.Student Attendance Record II (Hard)
    Description552.StudentAttendanceRecordII(Hard)Anattendancerecordforastudentcanberepresentedasastringwhereeachcharactersignifieswhetherthestudentwasabsent,late,orpresentonthatday.Therecordonlycontainsthefollowingthre......
  • 1483. Kth Ancestor of a Tree Node (Hard)
    Description1483.KthAncestorofaTreeNode(Hard)Youaregivenatreewithnnodesnumberedfrom0ton-1intheformofaparentarrayparentwhereparent[i]istheparentofithnode.Therootofthetreeisnode0.Findthekthancestorofagive......
  • 30 IIC(八)iic client
    源码1.iicclient创建方法1.1通过设备树直接创建只需要在对应i2c总线下指定设备信息即可示例:需要注意这里i2c1就是I2CBUS01.2通过用户空间直接去生成i2cclient创建i2cclientechonameaddr>/sys/bus/i2c/devices/i2c-n/new_devicei2c-n:i2cadapter删除i2cc......
  • 29 IIC(七)AP3216C
    1.简介AP3216C集成了光强(AmbilentLightSensor,ALS)、距离(ProximitySensor,PS)和红外传感器(InfraredRadiationLED,IR)。该芯片通过IIC接口与主控芯片交互实物图内部结构VDD:3.3VSLC:IICClockGND:LEDA:3.3VLEDC:一般接LDRLDR:LED驱动输出引脚INT:中断输......
  • 已安装过PageOfiice,谷歌浏览器反复提示PageOffice安装
    原因:Chrome开发团队以网络安全为由,强推ssl证书,希望所有部署在公网的网站,全部改用https访问,所以最新的谷歌和edge升级到94版本后对公网上的http请求下的非同域的http请求进行了拦截,于是就出现了目前遇到的反复提示安装pageoffice客户端的问题。解决方案:步骤1:打开谷歌浏览器,在浏览器......
  • 数列分段 III
    太菜了,只会打暴力。首先考虑二分答案。我们发现,有一个结论:如果每段和都小于\(mid\),那么可行划分的段数构成的集合\(S\)一定是一段区间。接下来证明。严谨证明太难写了,下面是半成品,没写完。说人话,就是归纳。假设前\(i-1\)个前缀满足,说明第\(i\)个前缀也满足。我们把......
  • 智能合约HardHat框架环境的搭建
    1.首先创建一个npm项目PSC:\Users\lcds\blockchainprojects>mkdirhardhatcontractPSC:\Users\lcds\blockchainprojects>cd.\hardhatcontract\2.运行 npminit-y  初始化项目PSC:\Users\lcds\blockchainprojects\hardhatcontract>npminit-yWrotetoC:\......
  • 【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证
    前言本章的OJ练习相对于OJ练习(4)较为简单。不过,本章的OJ最重要的是要我们证明为何可以这么做。这也是==面试==中常出现的。对于OJ练习(4):==->==传送门==<-==,分割链表以一种类似于归并的思想解得,回文链表以一种巧妙复用前面OJ题的思想解得。啰嗦一下:对于本章,最重要的是......
  • 图解LeetCode——437. 路径总和 III
    一、题目给定一个二叉树的根节点root ,和一个整数targetSum,求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。二、示例2.1>示例1:【输入】root=[10,5,-3,3,2,null......