GreedyProblem 7 of 35

Maximum trains for which stoppage can be provided

Brute Force
Time: O(m! * n)
Space: O(m)
Optimal
Time: O(n * m log m)
Space: O(m)

Problem Statement

Given n trains with their arrival times, departure times, and platform requirements, and m platforms at a station, find the maximum number of trains for which stoppage can be provided at the station.

Each train requires a specific platform and no two trains can use the same platform at the same time.

Constraints:

  • 1 ≤ n ≤ 10^4
  • 1 ≤ m ≤ 100
  • 0 ≤ arrival < departure ≤ 2359

Example:

  • Input:
    • n = 3, m = 2
    • Train 1: arrival=10:00, departure=10:30, platform=1
    • Train 2: arrival=10:15, departure=10:45, platform=1
    • Train 3: arrival=10:30, departure=11:00, platform=2
  • Output: 2
  • Explanation: Train 1 and Train 3 can stop (or Train 2 and Train 3).

Approach 1: Brute Force (Try All Combinations)

Intuition

Try all possible subsets of trains and check if each subset can be scheduled without conflicts.

Algorithm

  1. Generate all subsets of trains
  2. For each subset, group by platform
  3. Check if trains on same platform don't overlap
  4. Track maximum valid subset size
java
import java.util.*;

class Train {
    int arrival, departure, platform, index;
    
    Train(int arr, int dep, int plat, int idx) {
        arrival = arr;
        departure = dep;
        platform = plat;
        index = idx;
    }
}

public class Solution {
    private int maxTrains = 0;
    
    private boolean hasConflict(List<Train> subset) {
        Map<Integer, List<Train>> platforms = new HashMap<>();
        for (Train train : subset) {
            platforms.computeIfAbsent(train.platform, k -> new ArrayList<>()).add(train);
        }
        
        for (List<Train> trains : platforms.values()) {
            for (int i = 0; i < trains.size(); i++) {
                for (int j = i + 1; j < trains.size(); j++) {
                    Train t1 = trains.get(i), t2 = trains.get(j);
                    if (!(t1.departure <= t2.arrival || t2.departure <= t1.arrival)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    private void solve(Train[] trains, int idx, List<Train> current) {
        if (!hasConflict(current)) {
            maxTrains = Math.max(maxTrains, current.size());
        }
        
        if (idx == trains.length) return;
        
        current.add(trains[idx]);
        solve(trains, idx + 1, current);
        current.remove(current.size() - 1);
        
        solve(trains, idx + 1, current);
    }
    
    public int findMaxTrains(Train[] trains, int m) {
        maxTrains = 0;
        solve(trains, 0, new ArrayList<>());
        return maxTrains;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n * n^2) - 2^n subsets, O(n^2) conflict check
  • Space Complexity: O(n) - For current subset

Approach 2: Greedy (Activity Selection per Platform) - Optimal

Intuition

Apply activity selection independently to each platform. Sort trains by departure time and greedily select non-overlapping trains for each platform.

Algorithm

  1. Group trains by platform
  2. For each platform, sort trains by departure time
  3. Apply greedy activity selection to each platform
  4. Sum up selected trains from all platforms
java
import java.util.*;

class Train implements Comparable<Train> {
    int arrival, departure, platform;
    String name;
    
    Train(int arr, int dep, int plat, String name) {
        this.arrival = arr;
        this.departure = dep;
        this.platform = plat;
        this.name = name;
    }
    
    @Override
    public int compareTo(Train other) {
        return this.departure - other.departure;
    }
}

public class MaxTrainStoppage {
    public int findMaxTrains(List<Train> trains, int m) {
        // Group trains by platform
        Map<Integer, List<Train>> platformTrains = new HashMap<>();
        for (Train train : trains) {
            if (train.platform <= m) {
                platformTrains
                    .computeIfAbsent(train.platform, k -> new ArrayList<>())
                    .add(train);
            }
        }
        
        int totalTrains = 0;
        
        // Apply activity selection to each platform
        for (List<Train> pTrains : platformTrains.values()) {
            Collections.sort(pTrains);
            
            int count = 0;
            int lastDeparture = -1;
            
            for (Train train : pTrains) {
                if (train.arrival >= lastDeparture) {
                    count++;
                    lastDeparture = train.departure;
                }
            }
            
            totalTrains += count;
        }
        
        return totalTrains;
    }
    
    public List<Train> getSelectedTrains(List<Train> trains, int m) {
        Map<Integer, List<Train>> platformTrains = new HashMap<>();
        for (Train train : trains) {
            if (train.platform <= m) {
                platformTrains
                    .computeIfAbsent(train.platform, k -> new ArrayList<>())
                    .add(train);
            }
        }
        
        List<Train> selected = new ArrayList<>();
        
        for (List<Train> pTrains : platformTrains.values()) {
            Collections.sort(pTrains);
            
            int lastDeparture = -1;
            
            for (Train train : pTrains) {
                if (train.arrival >= lastDeparture) {
                    selected.add(train);
                    lastDeparture = train.departure;
                }
            }
        }
        
        return selected;
    }
    
    public static void main(String[] args) {
        MaxTrainStoppage mts = new MaxTrainStoppage();
        List<Train> trains = Arrays.asList(
            new Train(1000, 1030, 1, "Train1"),
            new Train(1015, 1045, 1, "Train2"),
            new Train(1030, 1100, 2, "Train3"),
            new Train(1100, 1130, 1, "Train4"),
            new Train(1045, 1115, 2, "Train5")
        );
        
        System.out.println("Max trains: " + mts.findMaxTrains(trains, 2));
    }
}

Dry Run Example

Trains: 1. Express1: Platform 1, 10:00 - 10:30 2. Local1: Platform 1, 10:15 - 10:45 3. Express2: Platform 2, 10:30 - 11:00 4. Express3: Platform 1, 11:00 - 11:30 5. Local2: Platform 2, 10:45 - 11:15 6. Express0: Platform 1, 09:00 - 09:30 m = 2 platforms Group by platform: Platform 1: [Express1, Local1, Express3, Express0] Platform 2: [Express2, Local2] Activity Selection for Platform 1: Sort by departure: [Express0(9:30), Express1(10:30), Local1(10:45), Express3(11:30)] Step 1: Express0 (9:00-9:30) - arrival 9:00 >= lastDep -1, select! - lastDep = 9:30 Step 2: Express1 (10:00-10:30) - arrival 10:00 >= lastDep 9:30, select! - lastDep = 10:30 Step 3: Local1 (10:15-10:45) - arrival 10:15 < lastDep 10:30, skip! Step 4: Express3 (11:00-11:30) - arrival 11:00 >= lastDep 10:30, select! - lastDep = 11:30 Platform 1 selected: 3 trains Activity Selection for Platform 2: Sort by departure: [Express2(11:00), Local2(11:15)] Step 1: Express2 (10:30-11:00) - arrival 10:30 >= lastDep -1, select! - lastDep = 11:00 Step 2: Local2 (10:45-11:15) - arrival 10:45 < lastDep 11:00, skip! Platform 2 selected: 1 train Total: 3 + 1 = 4 trains

Complexity Analysis

  • Time Complexity: O(n log n) where n is total number of trains
    • Grouping: O(n)
    • Sorting each platform: O(n log n) total
    • Selection: O(n)
  • Space Complexity: O(n) - For storing grouped trains

Key Takeaways

  1. Reduce to Activity Selection: Each platform is independent activity selection
  2. Group by Platform: Process each platform separately
  3. Sort by Departure: Key to greedy activity selection
  4. Non-overlapping Selection: Choose trains that don't conflict on same platform
  5. Platform Constraint: Train can only use its designated platform
  6. Time Encoding: Use integer format (HHMM) for easy comparison
  7. Real Application: Railway station scheduling, resource allocation
Previous
Greedy Algorithm to find Minimum number of Coins
Next
Minimum Platforms Problem