title: Algorithm to find maximum classes attended by student | activity selection problem
body: <p>Algorithm asked in one of the top company's interview, but I am not able to find a feasible solution. Need expert advice.</p>
  <p>Suppose a student wants to attend maximum number of classes in a collage in a day (without any class overlap).</p>
  <p><strong>Input Format</strong></p>
  <ul>
  <li>The first line contains an integer n which gives the number of subjects offered on that day.</li>
  <li>The next n lines follow containing the subject name (which is a string) followed by the start and end time for that subject in 24-hour format: hh:mm</li>
  </ul>
  <p><strong>For eg:</strong> <code>Maths 10:00 11:00</code><br />
  <strong>Note:</strong> The timings are given in a 24-hour format and the subject names do not have spaces between them.</p>
  <p><strong>Output Format</strong><br />
  The output should contain a number representing the maximum number of classes the student can choose.</p>
  <p><strong>Constraints</strong><br />
  <code>2 &lt;= n &lt;= 100</code><br />
  <code>start time of a class &lt; end time of class</code></p>
  <p><strong>Sample Input</strong></p>
  <pre><code>4
  Maths 16:00 18:00
  ComputerScience 12:00 13:00
  Physics 12:30 14:00
  Chemistry 14:00 16:30
  </code></pre>
  <p><strong>Sample Output</strong></p>
  <pre><code>2
  </code></pre>
  <p><strong>Explanation</strong><br />
  ComputerScience starts the earliest and ends the earliest, so we take it first. After that, we cannot take Physics because it starts before ComputerScience is over. So we will take the next class, that is, Chemistry. But after Chemistry we cannot take Maths as Maths class starts before Chemistry class ends. So we can schedule a maximum of 2 classes for the day.</p>
  <p>Below is my solution but I am not getting correct answer:</p>
  <pre class="lang-java prettyprint-override"><code>private void getMaxClass(String input) {
  
      Map&lt;String, Long&gt; classTime = new LinkedHashMap&lt;&gt;();
      Map&lt;String, List&lt;String&gt;&gt; timeMap = new LinkedHashMap&lt;&gt;();
      String[] split = input.split(&quot; &quot;);
      String subject = split[0];
      String StartTime = split[1];
      String endTime = split[2];
      List&lt;String&gt; lvalue = new ArrayList&lt;&gt;();
      lvalue.add(StartTime);
      lvalue.add(endTime);
      timeMap.put(subject, lvalue);
      long difference = FineDifferenceInTime(StartTime, endTime);
      classTime.put(subject, difference);
      int count = 0;
      Date date1 = null;
      Date date2 = null;
      Map&lt;String, Long&gt; sortedByValueDesc = classTime.entrySet().stream()
              .sorted(Map.Entry.&lt;String, Long&gt;comparingByValue())
              .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -&gt; e1, LinkedHashMap::new));
      for (Map.Entry&lt;String, Long&gt; entry : sortedByValueDesc.entrySet()) {
          String sub = entry.getKey();
          List&lt;String&gt; startEnd = timeMap.get(sub);
          Date dateBefore = null;
          Date dateAfter = null;
          SimpleDateFormat format = new SimpleDateFormat(&quot;HH:mm&quot;);
          try {
              dateBefore = format.parse(startEnd.get(0));
              dateAfter = format.parse(startEnd.get(1));
          } catch (ParseException e) {
              e.printStackTrace();
          }
          if (count == 0) {
              count++;
              try {
                  date1 = format.parse(startEnd.get(0));
                  date2 = format.parse(startEnd.get(1));
              } catch (ParseException e) {
                  e.printStackTrace();
              }
          }
          if (dateBefore.after(date1) &amp;&amp; dateBefore.before(date2)) {
              timeMap.remove(sub);
          }
      }
      System.out.println(timeMap.size());
  }
  </code></pre>