MinimumHallsOptimzed.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Lecture {
    int startTime;
    int endTime;

    public Lecture(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }
}

public class MinimumHallsOptimzed {

    public static int minHalls(List<Lecture> lectures) {
        List<Integer> startTimes = new ArrayList<>();
        List<Integer> endTimes = new ArrayList<>();

        for (Lecture lecture : lectures) {
            startTimes.add(lecture.startTime);
            endTimes.add(lecture.endTime);
        }

        Collections.sort(startTimes);
        Collections.sort(endTimes);

        int startPtr = 0;
        int endPtr = 0;
        int halls = 0;
        int currentHalls = 0;

        while (startPtr < startTimes.size()) {
            if (startTimes.get(startPtr) < endTimes.get(endPtr)) {
                currentHalls++;
                startPtr++;
            } else {
                currentHalls--;
                startPtr++;
                endPtr++;
            }

            halls = Math.max(halls, currentHalls);
        }

        return halls;
    }

    public static void main(String[] args) {
        List<Lecture> lectures = new ArrayList<>();
        lectures.add(new Lecture(9, 10));
        lectures.add(new Lecture(10, 11));
        lectures.add(new Lecture(11, 12));
        lectures.add(new Lecture(9, 12));

        int minimumHalls = minHalls(lectures);
        System.out.println("Minimum number of halls required: " + minimumHalls);
    }
}