FastPrep
Problem · Dynamic Programming

Get Minimum Time

Learn this problem
● MediumMicrosoft logoMicrosoftOA
See Microsoft hiring insights

Problem statement

A student at HackerSchool is provided with a schedule of n days, where each day can have up to m hours of lecture classes.

The schedule is represented by a binary matrix schedule[][], where schedule[i][j] = '1' means there is a lecture at the jth hour of the ith day, and schedule[i][j] = '0' means there is no lecture at that time.

If the student attends the first lecture at the xth hour and the last lecture at the yth hour on a single day, then they spend (y - x + 1) hours at school that day. The student is allowed to skip up to k lectures in total over all n days.

Determine the minimum total time (in hours) the student needs to attend school over all n days, given that they can skip lectures optimally.

Function

getMinimumTime(schedule: char[][], k: int) → int

Complete the function getMinimumTime in the editor with the following parameters:

  1. char schedule[n][m]: binary strings each of length m, which denote the schedule of the school
  2. int k: the number of lectures the student can skip

Returns

int: the minimum total time the student is required to attend the school.

Examples

Example 1

schedule = [['1', '0', '0', '0', '1']]k = 1return = 1
The student can skip the last lecture of the first day, that is, schedule[0][4]. Then, they only have to attend one lecture at the 0th hour, so the total time spent at school = 1, which is the minimum possible. Thus, the answer is 1.

Constraints

  • 1 <= k, m, n <= 200
  • schedule[i][j] == '0' or '1'
  • It is guaranteed that the length of each schedule[i] (0 <= i < n) is equal to m.

More Microsoft problems

drafts saved locally
public int getMinimumTime(char[][] schedule, int k) {
  // write your code here
}
schedule[['1', '0', '0', '0', '1']]
k1
expected1
checking account