0

Daily Challenge #20

Witaj w ten wspaniały (wolny) piątek! Czas na rozwiązanie kolejnego zadania, tym razem od firmy Snapchat. Zadanie nietrudne, wyceniłem na 2 gwiazdki, zapraszam do przeczytania i rozwiązania.

Tak jak zawsze, kod jest dostępny na GitHubie.

Wpis ten należy do cyklu Daily Challenge. W cyklu tym rozwiązuję każdego dnia nowe zadanie. Zadanie te traktuję w taki sposób, jakbym dostał je na rozmowie kwalifikacyjnej i miał coś wymyślić. Implementuję pierwszą myśl jaka przyjdzie mi do głowy. Nie musi być ona (zazwyczaj nie będzie) najlepszym rozwiązaniem. Chodzi po prostu o zabawę i sprawdzenie jakbym sobie poradził z podobnym wyzwaniem. Zaimplementowane rozwiązanie nie jest z reguły tłumaczone, jeżeli masz pytania możesz je zadawać w komentarzach. Wszystkie zadania udostępniane są subskrybentom Daily Coding Problem.

Zadanie

Dzisiejsze zadanie ma następującą treść:

Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.
For example, given [(30, 75), (0, 50), (60, 150)], you should return 2.

Aby to rozwiązać, musiałem skorzystać trochę z obiektowości, owszem można to zrobić inaczej, ale obiektowo jest czytelniej.

Testy

Dzisiaj w testach sprawdzany jest przypadek podany przez autora zadania oraz bardziej skomplikowany napisany osobiście. Kod wygląda następująco:

[TestMethod]
public void DailyChallenge20()
{
    DailyChallenge20 daily = new DailyChallenge20();
    Assert.AreEqual(2, daily.Proceed(new Tuple<int, int>[]
    {
        new Tuple<int, int>(30,75),
        new Tuple<int, int>(0,50),
        new Tuple<int, int>(60,150),
    }));
 
    Assert.AreEqual(3, daily.Proceed(new Tuple<int, int>[]
    {
        new Tuple<int, int>(10,15),
        new Tuple<int, int>(0,20),
        new Tuple<int, int>(15,25),
        new Tuple<int, int>(25,50),
        new Tuple<int, int>(5,25),
        new Tuple<int, int>(20,40),
    }));
}

Implementacja

W implementacji – jak wspomniałem wcześniej – skorzystałem z obiektów. Pozwoliło mi to ładnie zebrać i oddać wynik, a dodatkowo algorytm sprawdzający jest bardziej czytelny. Kod algorytmu wraz z dodatkowymi klasami wygląda następująco:

private class Room
{
    public List<Lecture> Lectures = new List<Lecture>();
}
 
private class Lecture
{
    public int Start;
    public int End;
}
 
public int Proceed(IEnumerable<Tuple<int,int>> data)
{
    IEnumerable<Tuple<int, int>> sorted = data.OrderBy(x => x.Item1);
    List<Room> rooms = new List<Room>();
    foreach (var lecture in sorted)
    {
        if (TryAddForExistingRoom(rooms, lecture))
        {
            continue;
        }
        Room room = new Room();
        room.Lectures.Add(new Lecture { Start = lecture.Item1, End = lecture.Item2 });
        rooms.Add(room);
    }
    return rooms.Count;
}
 
private bool TryAddForExistingRoom(List<Room> rooms, Tuple<int, int> lecture)
{
    foreach (var room in rooms)
    {
        Lecture lastLect = room.Lectures.Last();
        if (lecture.Item1 >= lastLect.End)
        {
            // Add on end
            room.Lectures.Add(new Lecture { Start = lecture.Item1, End = lecture.Item2 });
            return true;
        }
    }
    return false;
}

Mission Completed

I zrobione, kod napisany, testy przechodzą. Fajne ciekawe zadanie, trochę odstające od rutyny innych zadań.

Jeżeli Ty chciałbyś podesłać jakieś ciekawe zadanie, to nie krępuj się proszę i ślij na p.bogdanski@devmight.pl. Pamiętaj, że zadanie powinno nadawać się na rozmowę kwalifikacyjną, więc nie może to być problem, którego rozwiązanie zajmuje kilka godzin. Dzięki!

Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.