Search code examples
javatimecomplexity-theory

Can this code be optimized any further than this?

Given this challenge:

challenge

What I've tried:

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int A, B;
        long K;
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int M = input.nextInt();

        long[] array = new long[N];

        for(long i=1; i<=M; i++) {
            A = input.nextInt();
            B = input.nextInt();
            K = input.nextInt();
            for(int j=A; j<=B; j++) {
                array[j-1] += K;
            }
        }
       long max = 0;
       for(int i=1; i<array.length; i++) {
            if(max < array[i]) {
                max = array[i];
            }
        }
        System.out.println(max);
    }
}

The problem is: First 7 cases are correct except the last 7 - "Terminated Due to Time Out".

Solution

  • Friend i took your given problem and now finally solved: check out the optimized code , i took a different approach on this code. What I did is to store the changes given and then apply them please comment if you don't understand. Its working i have tested.

    import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

  public static void main(String[] args) {

      Scanner scn = new Scanner (System.in);

      int N = scn.nextInt();
      int M = scn.nextInt();

      Long [] hello = new Long [N+2];

      for (int pro = 0; pro < M ; pro++){
         int a = scn.nextInt();
         int b = scn.nextInt();
         long k = scn.nextInt();
         if (hello[a] == (Long) null) hello[a] = (long)0;
         if (hello[b+1] == (Long) null) hello [b+1] = (long)0;
         hello[a] += k;
         hello [b+1] += k * -1;

      }

    //compile the arry and find the largest
      boolean editLargest = true;
      Long largest = hello[0];
      long eK = 0;
      for (int pro = 0; pro < hello.length-1 ; pro++){
          if (hello [pro] == (Long)null)continue;
          if (editLargest){
                largest = hello[pro];
                editLargest = false;
          }
          eK += hello[pro];
          if (largest < eK) largest = eK;
      }
      System.out.println (largest);

  }
}

    checkout the screensort https://i.sstatic.net/lzqAq.png