HackerEarth challenge: Lunch boxes

Question

I was solving the lunch boxes problem on HackerEarth but as I submitted my solution most of the test cases were passed and the rest showed 'Time Limit Exceeded'. I would be very grateful if you could help me improve the algorithm of my code to reduce the runtime.

Following is the Problem

Alice works as a restaurant manager. The restaurant has prepared 'N' lunch boxes and Alice plans to distribute them to some schools. Consider that there are 'M' schools and an \$i^{th}\$ school orders \$A_i\$ lunch boxes.

She wants to distribute lunch boxes to as many schools as possible. Also, she has the following rule:

For an \$i^{th}\$ school, she gives either zero or \$A_i\$ lunch boxes

Your task is to help Alice to determine the maximum number of schools that can get lunch boxes.

Input format

• The first contains an integer \$t\$ that denotes the number of test cases in the input.
• Each test case consists of two lines:
  • The first line contains two integers \$N\$ and \$M\$.
  • The second line contains integers \$A_1, A_2, ..., A_m\$.

Constraints

• \$ 1 \le t \le 10 \$
• \$ 1 \le N, M \le 10^5 \$
• \$ 1 \le A_i \le 10^6 \$

My code

#include<stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        int n,m;
        scanf("%d", &n); 
        scanf("%d", &m); 
        int a[m];
        
        for(int i=0; i<m; i++){
            scanf("%d", &a[i]);   
        }
        
        for(int i=0; i<m; i++){
            for(int j=i + 1; j<m; j++){
                if(a[i] > a[j]){
                    int temp = a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }
            }
        }
       
       int sum=0, count=0;
       for(int i=0; i<m; i++){
          sum=sum+a[i];
          if(sum>n){
              break;
          }
          else if(sum<=n)
              count++;
    
          }
          printf("%d\n", count);
       }
       
    }

Answer 1

Use a better sorting algorithm

I think the main reason why you get a time limit exceeded error is because you are using an \$O(M^2)\$ algorithm to sort the orders. This is going to get slow very quickly for large values of \$M\$. While you could try to implement a better sorting algorithm yourself, use qsort() instead.

Use more meaningful variable names

You are using a lot of one-character variable names: t, n, m, a. It's very hard to understand what those variables mean without having to follow the whole code. If you are going to use the same names as used in the problem statement, or for example if you are implementing some algorithm or mathematical formula from a paper, make sure you use exactly the same names as the problem (so in this case, capital N, M and A), and add a comment to the code linking to the problem/paper/etc. where those things are described.

Alternatively, you could give them more meaningful names yourself:

• t -> num_testcases
• n -> num_lunchboxes
• m -> num_schools
• a[] -> order_sizes[]

The exception is for variables like i and j. These are very commonly used as iteration counters, so it's not going to be confusing for most programmers.

Unnecessary else if

Don't add an if after an else if the condition is just the inverse of the first if. This will do just fine:

if (sum > n) {
    break;
} else {
    count++;
}

Avoiding having to repeat the condition ensures there is less change of mistakes. Also, you don't even need the else part in this code, you can just write:

if (sum > n) {
    break;
}

count++;