Maximize occupied cells in given Matrix satisfying the conditions

by

Looking at the matrix of dimensions N * m, the task is Maximize The total number of occupied cells in the specified array that follow the specified condition:

  • If two cells are occupied in the same row, then there must be at least one empty cell between them.
  • If two cells are occupied in different rows, there must be at least one completely empty row between them
    That is, if the cells in ith And y row occupied like this I So there must be a file K Completely empty row like that I .

Examples:

entrance: n = 1, m = 5
Produce: 3
Explanation: There is only one row of five seats.
A maximum of three cells can be occupied.
See the table below where the number 1 indicates the occupied cell.

entrance: n = 3, m = 3
Produce: 4
Explanation: There are three rows with three seats each.
The maximum occupied cells can be 4.

naive approach: The problem can be solved using a greedy approach. Start filling from the first row and first column and keep a gap of 1 between any two occupied cells in one row and a one-row gap between two occupied cells of different rows.

Here is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int solve(int N, int M)

{

    int ans = 0;

    while (1) {

        

        

        for (int i = 1; i <= M; i += 2) {

            ans++;

        }

        

        

        

        

        

        if (N >= 2) {

            N--;

            N--;

        }

        else if (N == 1) {

            N--;

        }

        if (N == 0) {

            break;

        }

    }

  

    

    return ans;

}

int main()

{

    int N = 1;

    int M = 5;

    cout << solve(N, M);

    return 0;

}

Java

import java.util.*;

public class GFG

{

  

  

  static int solve(int N, int M)

  {

    int ans = 0;

    while (true)

    {

      

      

      for (int i = 1; i <= M; i += 2) {

        ans++;

      }

      

      

      

      

      

      if (N >= 2) {

        N--;

        N--;

      }

      else if (N == 1) {

        N--;

      }

      if (N == 0) {

        break;

      }

    }

    

    return ans;

  }

  

  public static void main(String[] args)

  {

    int N = 1;

    int M = 5;

    System.out.print(solve(N, M));

  }

}

Python 3

def solve(N, M):

    ans = 0;

    while (1):

    

        

        

        for i in range(1, M + 1, 2):

            ans += 1

        

        

        

        

        

        

        if (N >= 2):

            N -= 1

            N -= 1

        elif (N == 1):

            N -= 1

        if (N == 0):

            break

  

    

    return ans;

N = 1;

M = 5;

print(solve(N, M));

bad #

using System;

class GFG {

  

  

  static int solve(int N, int M)

  {

    int ans = 0;

    while (true)

    {

      

      

      for (int i = 1; i <= M; i += 2) {

        ans++;

      }

      

      

      

      

      

      if (N >= 2) {

        N--;

        N--;

      }

      else if (N == 1) {

        N--;

      }

      if (N == 0) {

        break;

      }

    }

    

    return ans;

  }

  

  public static void Main()

  {

    int N = 1;

    int M = 5;

    Console.Write(solve(N, M));

  }

}

JavaScript

<script>

function solve(N, M)

{

    let ans = 0;

    while (1)

    {

    

        

        

        for (let i = 1; i <= M; i += 2) {

            ans++;

        }

        

        

        

        

        

        

        if (N >= 2) {

            N--;

            N--;

        }

        else if (N == 1) {

            N--;

        }

        if (N == 0) {

            break;

        }

    }

  

    

    return ans;

}

let N = 1;

let M = 5;

document.write(solve(N, M));

</script>

time complexity: O (N * M)
Additional space: oh (1)

Active approach: To maximize the total number of occupied cells, they should be filled in the above manner. The total number can be obtained from the following observation:

So, the maximum number of cells that can be occupied per row is ceiling (m / 2).
Since there is a single row gap between any two occupied cells of different rows,
The maximum number of rows that can be filled is Ceiling (N/2).
And therefore Maximum The number of cells that can be occupied is Ceiling (m/2) * Ceiling (N/2).

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int solve(int N, int M)

{

    int x = (M + 1) / 2;

    int y = (N + 1) / 2;

    int ans = x * y;

    

    return ans;

}

int main()

{

    int N = 1;

    int M = 5;

    cout << solve(N, M);

    return 0;

}

Java

import java.io.*;

class GFG

{

  

  

  public static int solve(int N, int M)

  {

    int x = (M + 1) / 2;

    int y = (N + 1) / 2;

    int ans = x * y;

    

    return ans;

  }

  

  public static void main (String[] args)

  {

    int N = 1;

    int M = 5;

    System.out.print(solve(N, M));

  }

}

JavaScript

<script>

        

        

        

        const solve = (N, M) => {

            let x = parseInt((M + 1) / 2);

            let y = parseInt((N + 1) / 2);

            let ans = x * y;

            

            return ans;

        }

        

        let N = 1;

        let M = 5;

        document.write(solve(N, M));

    

    </script>

time complexity: oh (1)
Additional space: oh (1)

Leave a Comment